一. 链表 7 Copy List with Random P

思路：

先建立一个具有相同next pointer的list，将old list的next指向new list里相应的node。再将new list里node的random指向old list 的对应node。这里我们只需要将new list 的random指针弄好即可。
new list 里的random指针只需要沿着node.random.random.next 就可以得到相应值。

"""
Definition for singly-linked list with a random pointer.
class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None
"""


class Solution:
    # @param head: A RandomListNode
    # @return: A RandomListNode
    def copyRandomList(self, head):
        # write your code here
        
        # create a new list with the same value and next pointer, 
       # lead the random pointer of new list to its bro in the old list
        node = head
        duplicate_node = RandomListNode(node.label)
        duplicate_node.random = node
        node_1 = duplicate_node
        while node.next:
            node = node.next 
            new_duplicate_node = RandomListNode(node.label)
            
            new_duplicate_node.random = node
            node_1.next = new_duplicate_node
            node_1 = new_duplicate_node 
        
        # point the next pointer of old list to the corresponding node in the new list
        node = head
        node_1 = duplicate_node
        while node:
            next = node.next
            node.next = node_1
            node_1 = node_1.next
            node = next
        
        node = head
        node_1 = duplicate_node
        
        # build the random pointers of the new list 
        while node_1:
            if not node_1.random:
                break
            if node_1.random.random:
                node_1.random = node_1.random.random
            else:
                node_1.random = None
            
            node.next = node_1.random
            node_1 = node_1.next
    
        return duplicate_node