原题

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

要求返回这个链表的深度拷贝。

思路

先对链表进行一次遍历，在遍历过程中复制每一个链表节点。同时考虑到要复制随机指针，在遍历的同时创建原始链表节点和复制后的链表节点的关系，此处python中用dict，类似哈希的方式存储两者的对应关系。

再对复制后的链表进行一次遍历，遍历过程中根据存下的对应关系修改复制节点中随机指针的值。

代码

# Definition for singly-linked list with a random pointer.

# class RandomListNode(object):

#    def __init__(self, x):

#        self.label = x

#        self.next = None

#        self.random = None

class Solution(object):

    def copyRandomList(self, head):

        """

        :type head: RandomListNode

        :rtype: RandomListNode

        """

        dummy = RandomListNode(0)

        ori = head

        cp = dummy

        ori_cp_dict = {}     

        while(ori):

            cp.next = RandomListNode(ori.label)

            cp.next.random = ori.random

            ori_cp_dict[ori] = cp.next

            ori = ori.next

            cp = cp.next

        cp = dummy.next

        while(cp):

            if cp.random:

                cp.random = ori_cp_dict[cp.random]

            cp = cp.next 

        return dummy.next