剑指offer-25、复杂链表的复制

题⽬描述

输⼊⼀个复杂链表（每个节点中有节点值，以及两个指针，⼀个指向下⼀个节点，另⼀个特殊指针random 指向⼀个随机节点），请对此链表进⾏深拷⻉，并返回拷⻉后的头结点。（注意，输出结果中请不要返回参数中的节点引⽤，否则判题程序会直接返回空）

思路及解答

哈希表映射

使用哈希表存储原节点和新节点的映射关系：

• 第一次遍历：创建所有新节点，并建立原节点到新节点的映射
  
• 第二次遍历：根据映射关系设置新节点的next和random指针
  

1. public class Solution {
2.     public Node copyRandomList(Node head) {
3.         if (head == null) {
4.             return null;
5.         }
6.         
7.         // 创建哈希表存储原节点到新节点的映射
8.         HashMap<Node, Node> map = new HashMap<>();
9.         Node current = head;
10.         
11.         // 第一次遍历：创建所有新节点并建立映射
12.         while (current != null) {
13.             map.put(current, new Node(current.val));
14.             current = current.next;
15.         }
16.         
17.         // 第二次遍历：设置新节点的next和random指针
18.         current = head;
19.         while (current != null) {
20.             Node newNode = map.get(current);
21.             newNode.next = map.get(current.next);
22.             newNode.random = map.get(current.random);
23.             current = current.next;
24.         }
25.         
26.         return map.get(head);
27.     }
28. }
30. class Node {
31.     int val;
32.     Node next;
33.     Node random;
34.    
35.     public Node(int val) {
36.         this.val = val;
37.         this.next = null;
38.         this.random = null;
39.     }
40. }

复制代码

• ​时间复杂度​：O(n)，两次遍历链表
  
• ​空间复杂度​：O(n)，需要存储所有节点的映射关系
  

节点插入拆分法

通过在原链表中插入新节点来避免使用额外空间：

• ​节点复制插入​：在每个原节点后面插入一个复制的新节点
  
• ​设置random指针​：新节点的random指向原节点random的下一个节点
  
• ​链表拆分​：将混合链表拆分为原链表和新链表
  

1. public class Solution {
2.     public Node copyRandomList(Node head) {
3.         if (head == null) {
4.             return null;
5.         }
6.         
7.         // 第一步：在每个节点后面插入复制的节点
8.         Node current = head;
9.         while (current != null) {
10.             Node newNode = new Node(current.val);
11.             newNode.next = current.next;
12.             current.next = newNode;
13.             current = newNode.next;
14.         }
15.         
16.         // 第二步：设置复制节点的random指针
17.         current = head;
18.         while (current != null) {
19.             if (current.random != null) {
20.                 current.next.random = current.random.next;
21.             }
22.             current = current.next.next;
23.         }
24.         
25.         // 第三步：拆分链表
26.         Node newHead = head.next;
27.         current = head;
28.         while (current != null) {
29.             Node temp = current.next;
30.             current.next = temp.next;
31.             if (temp.next != null) {
32.                 temp.next = temp.next.next;
33.             }
34.             current = current.next;
35.         }
36.         
37.         return newHead;
38.     }
39. }

复制代码

• ​时间复杂度​：O(n)，三次遍历链表
  
• ​空间复杂度​：O(1)，只使用固定数量的指针变量
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！