[daiy4] copy of JZ35 complex linked list

subject

answer ：

Can't understand the topic , Like input and output ？？
Oh ！ It turns out that each node is followed by a next Pointers and random Pointer oh

idea ：
Use one list Store all random node , Then add them to the regular linked list .
however null Nodes cannot be added next 了 , And in the beginning dummy=pHead, Then there will always be random There is ...

Ah! w(ﾟДﾟ)w, So I made a mistake ！！ The topic is asking for deep copy , It's not about connecting nodes ！

Ideas ： Build a dictionary ,key It is the present. node Value ,value yes random Value ; Then traverse the dictionary .

class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None

class Solution:
    #  return  RandomListNode
    def Clone(self, pHead):
        # write code here
        if pHead is None:
            return None
        res = RandomListNode(0)
        node_dict = dict()

        cur = pHead
        while cur:
            node_dict[cur.label] = cur.random
            cur = cur.next

        dummy = res
        for node,random1 in node_dict.items():
            res.next = RandomListNode(node)
            res = res.next
            res.random = random1

        return dummy.next

Refer to the answer ：

The idea is a little similar , It also creates a hash table ,key Is the current node ,value Is the value of the node ;
Then traverse the original linked list again , Original next and random Take it out

class Solution:
    #  return  RandomListNode
    def Clone(self, pHead):
        # write code here
        if  pHead is None:
            return None   
        dict = {
    }
        cur = pHead
        while cur:
            dict[cur] = RandomListNode(cur.label)
            cur = cur.next
        cur = pHead
        while cur:
            dict[cur].next = dict.get(cur.next)
            dict[cur].random = dict.get(cur.random)
            cur = cur.next
        return dict[pHead]