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.
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.