【题解】剑指Offer-34 复杂链表的复制

复杂链表的复制(剑指Offer-34)

题面

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

示例

示例 1:

1
2
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

1
2
输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]

示例 3:

1
2
输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

示例 4:

1
2
3
输入:head = []
输出:[]
解释:给定的链表为空(空指针),因此返回 null。

限制

1
2
3
-10000 <= Node.val <= 10000
Node.random 为空(null)或指向链表中的节点。
节点数目不超过 1000

思路

  • 复制各节点,构建拼接链表: 设原链表为 node1 → node2 → ⋯,构建的拼接链表如下所示: node1 → node1new → node2 → node2new → ⋯

  • 构建新链表各节点的 random 指向: 当访问原节点 cur 的随机指向节点 cur.random 时,对应新节点 cur.next 的随机指向节点为 cur.random.next 。

  • 拆分原 / 新链表: 设置 pre / cur 分别指向原 / 新链表头节点,遍历执行 pre.next = pre.next.next 和 cur.next = cur.next.next 将两链表拆分开。

  • 返回新链表的头节点 res 即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr) return nullptr;
Node *cur = head;

while(cur != nullptr){
Node *t = new Node(cur->val);
t->next = cur->next;
cur->next = t;
cur = t->next;
}

cur = head;
while(cur != nullptr){
if(cur->random != nullptr)
cur->next->random = cur->random->next;
cur = cur->next->next;
}

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;
}
};