拷贝具有随机指针的链表.md

copy-list-with-random-pointer(拷贝具有随机指针的链表)

知识点：链表

题目描述

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

给出链表，每个节点包含一个额外的随机指针，该指针可以指向列表中的任何节点或为空。

返回列表的深拷贝。

解题思路

上图为原始链表，黑色箭头代表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

代码

这里