复杂链表的复制

1. 题目描述

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

2. 思路分析

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

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

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

3. 代码分析

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
}