剑指Offer:复杂链表的复制

题目

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

分析

由于该题中的链表给每个节点都添加了一个指向任意节点的指针。假设,原始链表中的某个节点N,他得random指针指向节点S,由于S在链表中可能在N的前面也可能在N的后面。所以要定位S的位置要从原始链表的头节点开始。这中方法的时间复杂度为O(n^2), Too Slow

下面我们介绍一种在不用辅助空间的情况下实现O(n)的时间效率。

分三步

第一步:根据原始链表的每个节点N创建对应的N’ 我们把N‘ 链接在N的后面。

1
2
3
4
5
6
7
8
9
10
11
public void CloneNode(RandomListNode pHead) {
RandomListNode pNode = pHead;
while (pNode != null) {
RandomListNode pClone = new RandomListNode(0);
pClone.label= pNode.label;
pClone.next = pNode.next;
pClone.random = null;
pNode.next = pClone;
pNode = pClone.next;
}
}

第二步:设置复制出来的节点的random。 假设原始链表上的N的random 指向节点S,那么对应复制出来的N’是N的random指向的节点。同样S’是S的random指向的节点。

1
2
3
4
5
6
7
8
9
10
public void ConnectNode(RandomListNode pHead) {
RandomListNode pNode = pHead;
while (pNode != null) {
RandomListNode pClone = pNode.next;
if (pNode.random != null) {
pClone.random = pNode.random.next;
}
pNode = pClone.next;
}
}

第三步:将复制之后的长链表拆分为两个链表,把奇数位置上的节点用next链接起来的就是原始链表。把偶数位置上的节点用next链接起来的就是复制出来的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public RandomListNode ReconnectNode(RandomListNode pHead) {
RandomListNode pNode = pHead;
RandomListNode pCloneHead = null;
RandomListNode pCloneNode = null;

if (pNode != null) {
pCloneHead = pNode.next;
pCloneNode = pNode.next;
pNode.next = pCloneNode.next;
pNode = pNode.next;
}

while (pNode != null) {
pCloneNode.next = pNode.next;
pCloneNode = pCloneNode.next;
pNode.next = pCloneNode.next;
pNode = pNode.next;
}
return pCloneHead;
}

最后,结合上面三步的代码就是完整的代码。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;

RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public void CloneNode(RandomListNode pHead) {
RandomListNode pNode = pHead;
while (pNode != null) {
RandomListNode pClone = new RandomListNode(0);
pClone.label= pNode.label;
pClone.next = pNode.next;
pClone.random = null;
pNode.next = pClone;
pNode = pClone.next;
}
}

public void ConnectNode(RandomListNode pHead) {
RandomListNode pNode = pHead;
while (pNode != null) {
RandomListNode pClone = pNode.next;
if (pNode.random != null) {
pClone.random = pNode.random.next;
}
pNode = pClone.next;
}
}

public RandomListNode ReconnectNode(RandomListNode pHead) {
RandomListNode pNode = pHead;
RandomListNode pCloneHead = null;
RandomListNode pCloneNode = null;

if (pNode != null) {
pCloneHead = pNode.next;
pCloneNode = pNode.next;
pNode.next = pCloneNode.next;
pNode = pNode.next;
}

while (pNode != null) {
pCloneNode.next = pNode.next;
pCloneNode = pCloneNode.next;
pNode.next = pCloneNode.next;
pNode = pNode.next;
}
return pCloneHead;
}

public RandomListNode Clone(RandomListNode pHead) {
CloneNode(pHead);
ConnectNode(pHead);
return ReconnectNode(pHead);
}
}