复杂链表的复制.md

复杂链表的复制

知识点：

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解题思路

上图为原始链表，黑色箭头代表next指针，绿色箭头代表random指针。

第一步，复制每一个节点并将其插入到原来的链表中：

红色的节点即为复制的节点

第二步，根据原来节点的random指针更新复制的节点的random：

currentNode = pHead
        while currentNode is not None:
            node = currentNode.next
            if currentNode.random is not None:
                node.random = currentNode.random.next
            currentNode = node.next

第三步：分离出复制的节点们构成复制的链表：

  cloneP = pHead.next

        while currentNode.next is not None:
            temp = currentNode.next
            currentNode.next = temp.next
            currentNode = temp

代码

这里