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

About the author

is a Staff 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