Skip to main content

Flatten a folded linked list in python

Python program for Flatten a folded linked list. Here problem description and explanation.

#  Python 3 program for
#  Unfold a folded linked list OR
#  flatten folded linked list

#  Linked list node
class LinkNode :
	def __init__(self, data) :
		self.data = data
		self.next = None
	

class SingleLL :
	def __init__(self) :
		self.head = None
	
	#  Insert node at the beginning of linked list
	def addNode(self, data) :
		#  Create node
		node = LinkNode(data)
		node.next = self.head
		#  Set new head
		self.head = node
	
	#  Display linked list element
	def display(self) :
		if (self.head == None) :
			return
		
		temp = self.head
		#  iterating linked list elements
		while (temp != None) :
			print("", temp.data , end = " →")
			#  Visit to next node
			temp = temp.next
		
		print(" NULL")
	
	#  This is handle the request of unfold given linked list nodes
	def unfoldList(self) :
		if (self.head == None) :
			print("\n Empty linked list")
			return
		
		temp = self.head
		auxiliary = None
		hold = None
		#  Loop which is separating the fold elements 
		while (temp.next != None) :
			#  Get the second element
			hold = temp.next
			if (hold.next != None) :
				#  When exists pair of three elements
				temp.next = hold.next
				#  Visit to 3rd element
				temp = hold.next
			else :
				#  When get last two elements
				temp.next = None
			
			#  Add new node at beginning of auxiliary linked list
			hold.next = auxiliary
			#  Make new head node
			auxiliary = hold
		
		if (temp != None) :
			#  Combine lists
			temp.next = auxiliary
		
	

def main() :
	#  Create a empty linked lists
	sll1 = SingleLL()
	sll2 = SingleLL()
	#   Constructed first linked list
	#   2 → 5 → 1 → 8 → 10 → 4 → 9 → 7 → NULL
	sll1.addNode(7)
	sll1.addNode(9)
	sll1.addNode(4)
	sll1.addNode(10)
	sll1.addNode(8)
	sll1.addNode(1)
	sll1.addNode(5)
	sll1.addNode(2)
	#  Constructed second linked list
	#  1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
	sll2.addNode(7)
	sll2.addNode(6)
	sll2.addNode(5)
	sll2.addNode(4)
	sll2.addNode(3)
	sll2.addNode(2)
	sll2.addNode(1)
	#  Test A
	print(" Before unfold")
	sll1.display()
	sll1.unfoldList()
	print(" After unfold")
	sll1.display()
	#  Test B
	print(" Before unfold")
	sll2.display()
	sll2.unfoldList()
	print(" After unfold")
	sll2.display()

if __name__ == "__main__": main()

Output

 Before unfold
 2 → 5 → 1 → 8 → 10 → 4 → 9 → 7 → NULL
 After unfold
 2 → 1 → 10 → 9 → 7 → 4 → 8 → 5 → NULL
 Before unfold
 1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
 After unfold
 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment