这道题的难点在于如何正确处理random指针的复制。
常规思路是使用哈希表建立旧节点到新节点的映射,但这需要O(n)的额外空间。
本文介绍一种空间复杂度O(1)的解法,核心是:
在原链表的每个节点后面紧跟着插入一个克隆节点。
1.创建克隆节点并插入原链表
遍历原链表,在每个原节点后面插入一个值相同的新节点,形成交替结构。
1
2
3
4
5
6
7
8
9
|
Node cur = head;
Node next = null;
while (cur != null) {
next = cur.next; // 保存下一个原节点
cur.next = new Node(cur.val); // 创建克隆节点
cur.next.next = next; // 克隆节点指向下一个原节点
cur = next; // 移动到下一个原节点
}
|
2.设置克隆节点的random指针
由于克隆节点紧跟在原节点后面，如果原节点A的random指向节点B，那么A的克隆节点A’的random应该指向B的克隆节点B’，而B’恰好就是B.next。
1
2
3
4
5
6
7
8
9
10
11
|
cur = head;
Node copy = null;
while (cur != null) {
next = cur.next.next; // 下一个原节点
copy = cur.next; // 当前的克隆节点
// 如果原节点的random不为空,
// 则克隆节点的random指向原节点random的下一个节点(即克隆节点)
copy.random = cur.random != null ? cur.random.next : null;
cur = next;
}
|
3.分离新旧链表
把交织在一起的新旧链表分离开,恢复原链表的结构,同时得到独立的新链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
Node ans = head.next; // 新链表的头节点
cur = head;
while (cur != null) {
next = cur.next.next; // 下一个原节点
copy = cur.next; // 当前克隆节点
cur.next = next; // 恢复原链表连接
// 连接克隆链表
copy.next = next != null ? next.next : null;
cur = next;
}
return ans;
|
完整代码：
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
|
public static Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Node next = null;
// 创建克隆节点并插入
while (cur != null) {
next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
cur = head;
Node copy = null;
// 设置random指针
while (cur != null) {
next = cur.next.next;
copy = cur.next;
copy.random = cur.random != null ? cur.random.next : null;
cur = next;
}
Node ans = head.next;
cur = head;
// 分离链表
while (cur != null) {
next = cur.next.next;
copy = cur.next;
cur.next = next;
copy.next = next != null ? next.next : null;
cur = next;
}
return ans;
}
|