138. Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
Solution: HashMap
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if not head:
return None
clone = dict()
cur = head
while cur:
clone[cur] = RandomListNode(cur.label)
cur = cur.next
cur = head
while cur:
if cur.next:
clone[cur].next = clone[cur.next]
if cur.random:
clone[cur].random = clone[cur.random]
cur = cur.next
return clone[head]
Solution: O(1) space
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if not head:
return None
# simulate hash-map
cur = head
while cur:
copy = RandomListNode(cur.label)
cur.next, copy.next = copy, cur.next
cur = copy.next
# copy random pointers
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# separate clone from orignal
cur = head
clone = head.next
while cur:
copy = cur.next
cur.next = copy.next
if copy.next:
copy.next = copy.next.next
cur = cur.next
return clone