Friedrich Ewald My Personal Website

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
One way to solve this is to copy first all the nodes into a new list via the 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.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.

Related Posts