1. 题目描述

请实现函数ComplexListNode *Clone(ComplexListNode* pHead),复制一个复杂链表。在复杂链表中,每个结点除了有一个 next 指针指向下一个结点外,还有一个 sibling 指向链表中的任意结点或者 NULL。

2. 思路分析

按照正常的思路,首先从头到尾遍历链表,拷贝每个节点的 value 和 next 指针。然后从头再次遍历,第二次遍历的目的在于拷贝每个节点的 sibling 指针。

然而即使找到原节点的 sibling 指针,还是得为了找到复制节点对应的 sibling 指针而再遍历一遍。那么对于 n 个要寻找 sibling 指针的节点,复杂度就是 O(N*N)。

显然,为了降低复杂度,必须从第二次遍历着手。这里采用的方法是,在第一次遍历的时候,把 (原节点, 复制节点) 作为映射保存在表中。那么第二次遍历的时候,就能在 O(1) 的复杂度下立即找到原链上 sibling 指针在复制链上对应的映射。

3. 代码分析

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
class Node {
constructor(value, next = null, sibling = null) {
this.value = value
this.next = next
this.sibling = sibling
}
}

/**
* 复制复杂链表
* @param {Node} first
*/
function cloneNodes(first) {
if (!first) {
return null
}

const map = new Map()

let copyFirst = new Node(first.value),
node = first.next, // 被copy链的当前节点
last = copyFirst // copy链的当前节点, 此节点相对于被copy链短位移少1位

map.set(first, copyFirst)

while (node) {
last.next = new Node(node.value)
last = last.next
map.set(node, last)
node = node.next
}

// 第二次遍历, 迁移sibling
node = first
while (node) {
map.get(node) && (map.get(node).sibling = map.get(node.sibling))
node = node.next
}

return copyFirst
}

/**
* 测试代码
*/
const node1 = new Node('a'),
node2 = new Node('b'),
node3 = new Node('c'),
node4 = new Node('d')

node1.next = node2
node2.next = node3
node3.next = node4

node1.sibling = node3
node4.sibling = node2

let copyNode = cloneNodes(node1)
while (copyNode) {
console.log(copyNode)
copyNode = copyNode.next
}