clone_linked_list.py

class LNode:
  """defining a linked list node"""
  def __init__(self, value,next=None, random=None):
    self.value = value
    self.random = random
    self.next = next
  
  def __str__(self):
    return "(%s)"%(self.value)

def build_LL():
  """Let's build a Linked list"""
  a = LNode(10)
  b = LNode(20)
  c = LNode(30)
  d = LNode(40)
  e = LNode(50)

  head = None

  a.next = b
  b.next = c
  c.next = d
  d.next = e
  head = a
  return head

def clone_linked_list(head):
  if head is None:
    return 
  
  # Pass 1: clone the nodes into a hash table
  node = head
  clone_map = {}
  while node:
    clone_map[node] = LNode(node.value)
    node = node.next
  
  # Pass 2 : create the connections within those nodes
  node = head

  while node:
    clone_map[node].next = clone_map.get(node.next)

    # random_nodes can be cloned in constant time
    clone_map[node].random = clone_map.get(node.random)
    
    node = node.next

  
  return clone_map[head]


  


# driver program

head = build_LL()
cloned_head = clone_linked_list(head)
while cloned_head:
  print(cloned_head)
  cloned_head = cloned_head.next