138. Copy List with Random Pointer

# 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
        """
        if head is None:
            return head
        
        dummy = RandomListNode(-1)
        cur = dummy
        curOld = head
        mapping = {}
        mapping[None] = None
        while(curOld):
            cur.next = RandomListNode(curOld.label)
            mapping[curOld] = cur.next
            cur = cur.next
            curOld = curOld.next
            
        cur = dummy
        curOld = head
        while(curOld):
            cur.next.random = mapping[curOld.random] # when random is None, traversing linked list won't add none in the dictionary, we need to do it manually
            cur = cur.next
            curOld = curOld.next
            
        return dummy.next
        '''

Use dictionary to map old nodes (as key) to new nodes (as value). So that we could traverse old & new list together and know which new list node should be set as random reference.

# 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
        """
        if head is None:
            return head
        
        cur = head
        while(cur):
            nextNode = cur.next
            cur.next = RandomListNode(cur.label) # 5）用前后相邻顺序替代 dictionary 的映射关系，降低额外空间的占用；遇到要优化的算法时，尝试转换思路，什么东西可以【在功能上替代】传统的简单思路
            cur.next.next = nextNode
            cur = nextNode
        
        cur = head    
        while(cur):
            if cur.random: # 1) any next in linked list should be validated;
                cur.next.random = cur.random.next # 2) 如果一边加 random 一边去掉新旧之间的 link，会导致后面的新 node 指前面 新 node 时 找不到了，所以必须用两个循环来处理
            cur = cur.next.next # 3）修改代码时，时刻double check 逻辑是否正确
            
        cur = head
        dummy = RandomListNode(-1)
        newCur = dummy
        while(cur):
            newCur.next = cur.next # 4）跳着连接时，先处理中间值再对前后处理
            cur.next = cur.next.next
            cur = cur.next
            newCur = newCur.next
        
        return dummy.next
        

• See 1) 2) 3) 4) 5) in the code comments

• To summary, by inserting new node after old node, we could replace the mapping relationship. The core algorithm is :

  if cur.random: # 1) any next in linked list should be validated;
      cur.next.random = cur.random.next # 2) 如果一边加 random 一边去掉新旧之间的 link，会导致后面的新 node 指前面 新 node 时 找不到了，所以必须用两个循环来处理