题目链接：点击打开链接
题目大意：略。
解题思路：解决方案(2)解析。
相关企业
- 字节跳动
- 亚马逊（Amazon）
- 微软（Microsoft）
- 彭博（Bloomberg）
- 谷歌（Google）
- Shopee
- VMware
AC 代码
- Java
/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ // 解决方案(1) class Solution { public Node copyRandomList(Node head) { Node node = head; Map<Node, Node> map = new HashMap<>(); while (null != node) { map.put(node, new Node(node.val)); node = node.next; } node = head; while (null != node) { Node tmp = map.get(node); tmp.next = map.get(node.next); tmp.random = map.get(node.random); node = node.next; } return map.get(head); } } // 解决方案(2) class Solution { public Node copyRandomList(Node head) { if(head == null) return null; Node cur = head; // 1. 复制各节点，并构建拼接链表 while(cur != null) { Node tmp = new Node(cur.val); tmp.next = cur.next; cur.next = tmp; cur = tmp.next; } // 2. 构建各新节点的 random 指向 cur = head; while(cur != null) { if(cur.random != null) cur.next.random = cur.random.next; cur = cur.next.next; } // 3. 拆分两链表 cur = head.next; Node pre = head, res = head.next; while(cur.next != null) { pre.next = pre.next.next; cur.next = cur.next.next; pre = pre.next; cur = cur.next; } pre.next = null; // 单独处理原链表尾节点 return res; // 返回新链表头节点 } }
- C++
// 解决方案(1) class Solution { public: Node* copyRandomList(Node* head) { if(head == nullptr) return nullptr; Node* cur = head; unordered_map<Node*, Node*> map; // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射 while(cur != nullptr) { map[cur] = new Node(cur->val); cur = cur->next; } cur = head; // 4. 构建新链表的 next 和 random 指向 while(cur != nullptr) { map[cur]->next = map[cur->next]; map[cur]->random = map[cur->random]; cur = cur->next; } // 5. 返回新链表的头节点 return map[head]; } }; // 解决方案(2) class Solution { public: Node* copyRandomList(Node* head) { if(head == nullptr) return nullptr; Node* cur = head; // 1. 复制各节点，并构建拼接链表 while(cur != nullptr) { Node* tmp = new Node(cur->val); tmp->next = cur->next; cur->next = tmp; cur = tmp->next; } // 2. 构建各新节点的 random 指向 cur = head; while(cur != nullptr) { if(cur->random != nullptr) cur->next->random = cur->random->next; cur = cur->next->next; } // 3. 拆分两链表 cur = head->next; Node* pre = head, *res = head->next; while(cur->next != nullptr) { pre->next = pre->next->next; cur->next = cur->next->next; pre = pre->next; cur = cur->next; } pre->next = nullptr; // 单独处理原链表尾节点 return res; // 返回新链表头节点 } };
