Clone a linked list with random fields in python

Python program for Clone a linked list with random fields. Here problem description and other solutions.

#  Python 3 Program
#  Clone a linked list with next and random field

#  Linked List Node
class LinkNode :
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.next = None
		self.random = None
	

class MyLinkedList :
	def __init__(self) :
		self.head = None
	
	#  Add new node at the end of linked list
	def insert(self, value) :
		#  Create  node
		node = LinkNode(value)
		if (self.head == None) :
			self.head = node
		else :
			temp = self.head
			#  Find last node
			while (temp.next != None) :
				#  Visit to next node
				temp = temp.next
			
			#  Add node at last position
			temp.next = node
		
	
	#  Display linked list element
	def display(self) :
		if (self.head == None) :
			print("\nEmpty linked list")
			return
		
		temp = self.head
		print("\n ", end = "")
		while (temp != None) :
			if (temp != self.head) :
				print(end = "--->")
			
			if (temp.random != None) :
				print(temp.data ,"(", temp.random.data ,end = ")", sep="")
			else :
				print(temp.data, end = "")
			
			temp = temp.next
		
		print("-->NULL")
	
	#  Clone the linked list  with next and random field
	def cloneList(self) :
		if (self.head == None) :
			return None
		
		#  Define some auxiliary variable
		temp = None
		current = self.head
		node = None
		front = None
		#  Step 1
		#  Create and combine clone node
		while (current != None) :
			# Get current node of actual linked list
			temp = current
			#  Create clone node
			node = LinkNode(current.data)
			#  Visit to next node
			current = current.next
			#  Connect clone node after actual node
			temp.next = node
			#  Binding this clone to next upcoming
			#  nodes in actual linked list
			node.next = current
		
		#  Start to actual linked list
		current = self.head
		#  Step 2
		#  Set actual value of random field in clone linked list
		while (current != None and current.next != None) :
			#  Clone list node
			node = current.next
			if (current.random != None) :
				#  Set random node in clone linked list
				node.random = current.random.next
			
			#  Visit to actual linked list next node
			current = node.next
		
		#  Agian start to actual linked list
		current = self.head
		#  Step 3
		#  Separate actual and clone linked list
		while (current != None) :
			node = current.next
			if (front == None) :
				#  Get first node of clone linked list
				front = node
			
			current.next = node.next
			current = current.next
			if (current != None) :
				node.next = current.next
			else :
				node.next = None
			
		
		return front
	

def main() :
	#  Test linked list
	list1 = MyLinkedList()
	list2 = MyLinkedList()
	#  Create Normal linked list
	list1.insert(5)
	list1.insert(6)
	list1.insert(1)
	list1.insert(8)
	list1.insert(7)
	#   Simple linked list
	#   5 → 6 → 1 → 8 → 7 → NULL
	#   Set random node value
	#   ╷───────────┐
	#   │           │
	#   │   ╷───────│───┐
	#   ↓───│───╷   │   │
	#   ↓   ↓   ↑   │   │
	#   5 → 6 → 1 → 8 → 7 → NULL
	#   │   │       ↑   │
	#   └───│───────┘   │    
	#       │           │
	#       └───────────┘ 
	#    5(8)-->6(7)-->1(5)-->8(5)-->7(6)-->NULL
	#    Linked list with random field
	#  5-->8
	list1.head.random = list1.head.next.next.next
	#  6-->7
	list1.head.next.random = list1.head.next.next.next.next
	#  1 --> 5
	list1.head.next.next.random = list1.head
	#  8 --> 5
	list1.head.next.next.next.random = list1.head
	#  7 --> 6
	list1.head.next.next.next.next.random = list1.head.next
	list2.head = list1.cloneList()
	print("\n Actual Linked List", end = "")
	list1.display()
	print("\n Clone Linked List", end = "")
	list2.display()

if __name__ == "__main__": main()

Output

 Actual Linked List
 5(8)--->6(7)--->1(5)--->8(5)--->7(6)-->NULL

 Clone Linked List
 5(8)--->6(7)--->1(5)--->8(5)--->7(6)-->NULL