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
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