# 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 时 找不到了，所以必须用两个循环来处理
