复杂链表的复制

题目：请实现函数 ComplexListNode Clone(ComplexListNode root)，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 sbling 指针指向链表中的任意节点或者 null。复杂链表的节点定义如下：

private static class ComplexListNode {
    ComplexListNode next;
    ComplexListNode sibling;
    int value;
    public ComplexListNode(int value) {
        this.value = value;
    }
}

一个复杂链表的示例如下所示

看到这个问题，很多人的解决方案是首先复制链表的每一个节点，并使用 next 指针连接起来，第二步再次遍历链表，并且逐次设置 sbling 指针。考虑该链表的长度为 N，那么在每次设置 sbling 节点时都要搜索整个链表，搜索的时间复杂度是 $O(N)$，对于每一个节点都有这个搜索过程，所以整个时间复杂度为 $O(N^2)$。

现在我们可以考虑第二种方法，第一步仍然是根据原始链表的节点 N 创建复制的节点 N'，并将 <N,N'> 放入到一个哈希表中，那么这样一来，第二步就不需要去搜索整个链表，只需要以 $O(1)$ 的复杂度就可以从哈希表中拿到想要的节点。这种情况就是以空间换时间，我们需要 $O(N)$ 的空间复杂度把时间复杂度从 $O(N^2)$ 降到 $O(N)$。

现在我们在考虑一种方法，首先第一步还是根据原始链表的节点 N 复制节点 N'，并且将 N' 链接到 N 之后，如下所示

private static void cloneNodes(ComplexListNode root) {
    ComplexListNode cur = root;
    while (cur != null) {
        ComplexListNode cloneNode = new ComplexListNode(cur.value);
        cloneNode.next = cur.next;
        cur.next = cloneNode;
        cur = cloneNode.next;
    }
}

第二步设置复制出来的节点的 sbling，如果节点 N 的 sbling 指针指向的是 S，那么 N' 的 sbling 指向的就是 S.next，如下

private static void siblingNodes(ComplexListNode root) {
    ComplexListNode cur = root;
    while (cur != null) {
        if (cur.sibling != null) {
            cur.next.sibling = cur.sibling.next;
        }
        cur = cur.next.next;
    }
}

最后一步就是选择这些链表的第偶数个节点通过 next 连接起来，然后返回根节点

private static ComplexListNode reconnect(ComplexListNode root) {
    ComplexListNode cur = root;
    ComplexListNode cloneRoot = null;
    ComplexListNode curClone = null;
    if (cur != null) {
        cloneRoot = cur.next;
    }
    while (cur != null) {
        curClone = cur.next;
        cur = cur.next.next;
        curClone = curClone.next;
    }
    return cloneRoot;
}

我们把上面三步接合起来，就是复制链表的完整过程

public static ComplexListNode clone(ComplexListNode root) {
    cloneNodes(root);
    siblingNodes(root);
    return reconnect(root);
}