# 题目链接
# 题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的 head。
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9

# 解题思路
# 方法一
第一次遍历原链表时不考虑random指针,只是复制节点; 第二次遍历原链表时只考虑random指针。
/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* Random *Node
* }
*/
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
newHead := Node{
Val: head.Val,
Next: nil,
Random: nil,
}
p := head.Next
pre := &newHead
for p != nil {
newNode := &Node{
Val: p.Val,
Next: nil,
Random: nil,
}
pre.Next = newNode
p = p.Next
pre = pre.Next
}
p = head
newP := &newHead
for p != nil {
if p.Random != nil {
step := findStep(head, p.Random)
newP.Random = target(&newHead, step)
}
p = p.Next
newP = newP.Next
}
return &newHead
}
//确定从头结点到目标节点所经过的节点数
func findStep(head, target *Node) int {
p := head
step := 0
for p != target {
p = p.Next
step++
}
return step
}
//返回从头结点开始,走step步所到达的节点
func target(head *Node, step int) *Node {
p := head
for step > 0 {
p = p.Next
step--
}
return p
}
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
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
这种方法时间复杂度为O(n^2),主要耗时在于确定新节点的random指针上。
# 方法二
用空间换时间,使用map数据结构,保存原节点与新节点的对应关系,这样在确定random指针时可快速定位新节点。
/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* Random *Node
* }
*/
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
newHead := Node{
Val: head.Val,
Next: nil,
Random: nil,
}
p := head.Next
pre := &newHead
connection := make(map[*Node]*Node)
connection[head] = pre
for p != nil {
newNode := &Node{
Val: p.Val,
Next: nil,
Random: nil,
}
pre.Next = newNode
connection[p] = newNode
p = p.Next
pre = pre.Next
}
p = head
newP := &newHead
for p != nil {
if p.Random != nil {
newP.Random = connection[p.Random]
}
p = p.Next
newP = newP.Next
}
return &newHead
}
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
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
时间复杂度为O(n),空间复杂度为O(n)
# 方法三
将新节点先插入至对应原节点的后面,最后将新节点一一拆分出来。
/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* Random *Node
* }
*/
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
p := head
for p != nil {
newNode := &Node{
Val: p.Val,
Next: nil,
Random: nil,
}
newNode.Next = p.Next
p.Next = newNode
p = p.Next.Next
}
p = head
for p != nil {
if p.Random != nil {
p.Next.Random = p.Random.Next
}
p = p.Next.Next
}
newHead := head.Next
oldP := head
p = newHead
for p.Next != nil {
oldP.Next = oldP.Next.Next
p.Next = p.Next.Next
oldP = oldP.Next
p = p.Next
}
oldP.Next=nil
return newHead
}
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
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
注意:最后还需要将原链表复原,否则系统会报"Next pointer of node with label 7 from the original list was modified."这样的错误。
时间复杂度为O(n),空间复杂度为O(1)