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 } }
function cloneNodes(first) { if (!first) { return null }
const map = new Map()
let copyFirst = new Node(first.value), node = first.next, last = copyFirst
map.set(first, copyFirst)
while (node) { last.next = new Node(node.value) last = last.next map.set(node, last) node = node.next }
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 }
|