- 注意random指针可能指向None的情况，此时读取和插入map中的操作要小心。
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
if not head:
return head
dummy = Node(-1,None,None)
copycur = dummy
cur = head
copymap = {}
while cur:
if cur not in copymap.keys():
node = Node(cur.val, None, None)
copymap[cur] = node
# 注意cur.random为空的时候不要插入到copymap中
if cur.random and cur.random not in copymap:
node = Node(cur.random.val, None, None)
copymap[cur.random] = node
copycur.next = copymap[cur]
copycur = copycur.next
# 注意cur.random为空的时候copymap中查不到对应的value
if not cur.random:
copycur.random = None
else:
copycur.random = copymap[cur.random]
cur = cur.next
return dummy.next
- 解法二，空间复杂度O(1)，遍历三次(第一轮所有Node复制一份在原Node的后面，第二轮random指针的指向，第三轮拆分链表)。
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
if not head:
return head
# 第一轮,copy所有node
cur = head
while cur:
node = Node(cur.val, None, None)
last = cur.next
cur.next = node
node.next = last
cur = last
# 第二轮,完成random指针
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
else:
cur.next.random = None
cur = cur.next.next
# 第三轮,把链表拆开
cur = head
dummy = Node(-1, None, Node)
curcopy = dummy
while cur:
curcopy.next = cur.next
last = cur.next.next
cur.next = last
curcopy = curcopy.next
curcopy.next = None
cur = last
return dummy.next
