Leetcode: Copy list with random pointer
Given a head
of a list with pointers to next
and a random
element, copy the list to a new list without any random pointers pointing to the old list.
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
next
links. Next, we create two pointers, one pointing at the original list and the other one pointing at the new list. We then iterate over the original list (while moving the second pointer as well) and check at each step if we hit our current node in the original list via random
. If we do, we make a connection in the new list as well. One specialty is that two random
pointers can point at the same element. For this reason, we cannot simply stop once we found the first pointer but have to continue until the end.
This solution has to iterate multiple times over the same list as we start from the destination and not from the source. For a more efficient solution, see the altnerative solution below.
from typing import Optional
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
def __repr__(self) -> str:
"""Convenience method for debugging"""
return str(self.val)
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if head is None:
return None
p1 = head
# Copy first node manually
new_head = Node(head.val)
p2 = new_head
# Create single linked list
while p1.next is not None:
p2.next = Node(p1.next.val)
p2 = p2.next
p1 = p1.next
# Reset pointers
t1 = head
t2 = new_head
while t1 is not None:
p1 = head
p2 = new_head
while p1 is not None:
if p1.random == t1:
p2.random = t2
p1 = p1.next
p2 = p2.next
t1 = t1.next
t2 = t2.next
return new_head
if __name__ == '__main__':
s = Solution().copyRandomList
n = Node(1, Node(2, Node(3, Node(4))))
n.random = n.next.next
n.random.random = n.next.next.next
n.random.random.random = n.next
print(s(n))
n = Node(7, Node(13, Node(11, Node(10, Node(1)))))
n.next.random = n
n.next.next.random = n.next.next.next.next
n.next.next.next.random = n.next.next
n.next.next.next.next.random = n
print(s(n))
Runtime: 106 ms, faster than 5.23% of Python3 online submissions for Copy List with Random Pointer. Memory Usage: 15 MB, less than 46.50% of Python3 online submissions for Copy List with Random Pointer.
Alternate Solution
Another solution is to first interweave the new nodes with the old nodes such that after each original node, there’s a copy of the original node, pointing to the next node, and so on. When following for every node therandom
path, we just can set the next.random
to random.next
as the copy of the node comes always after the original node. This allows for a time complexity of O(3n)
.
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if head is None:
return head
# Step 1: Interweave new nodes in old list
curr = head
while curr is not None:
n = Node(x=curr.val, next=curr.next)
curr.next = n
curr = curr.next.next
# Step 2: Copy random pointers
curr = head
while curr is not None and curr.next is not None:
if curr.random is not None:
curr.next.random = curr.random.next
# Jump always 2 to avoid copied nodes
curr = curr.next.next
# Step 3: Isolate new nodes
curr = head.next
new_head = curr
while curr is not None:
if curr.next is not None:
curr.next = curr.next.next
curr = curr.next
return new_head