Linear Linked list can be reversed by manipulating the links of the individual nodes. Before writing Python Program to Reverse a Linear Linked List, its flow can be understood by following these steps.
- Identify current pointer, next pointer and the previous pointer
- Current pointer is initialized to first node of linked list and next and previous pointers are initialized to None
- Perform these steps in every iteration until the
last node of linear linked is reached
- Next pointer to be updated with link part of current node
- Link of current pointer is updated with previous pointer
- Current node becomes previous node by assigning current pointer to previous pointer
- Next Node becomes the current node by assigning next pointer to current pointer
- After the loop ends assign previous pointer to start pointer of the linear linked list.
Let’s understand the reversal process with the help of an example.
A Linked list is created storing names of some persons. The pointers are initialized to reverse linked list .
The pointers are repeatedly updated as indicated in the steps listed at the beginning. In the first step since the link part of first node is updated with prev and prev is initially Null, so it is Null. This will ensure that old first node is the new last node when the reversal of linked list is complete.
In the last step as soon as the link part of the last node is assigned the address of previous node, start pointer storing address of first node of linked list is assigned the last node. Now the linked list is reversed and the last node is the first node
Python Program to Reverse a Linear Linked List
class Node: def __init__(self, data=None, link=None): self.data=data self.link=link def __str__(self): return str(self.data) class LinearList: def __init__(self, start=None): self.start=start def printList(self): ptr=self.start while ptr: print(ptr) ptr=ptr.link print() def revList(self): curr=self.start prev=None nxt=None while curr: nxt=curr.link curr.link=prev prev=curr curr=nxt self.start= prev node1=Node('amy') node2=Node('Bob') node3=Node('Cathy') node4=Node('Dan') node5=Node('Eva') node6=Node('Fred') node7=Node('Zoe') node1.link=node2 node2.link=node3 node3.link=node4 node4.link=node5 node5.link=node6 node6.link=node7 ll=LinearList(node1) print("Linked List Initially") ll.printList() ll.revList() print("Linked List after Reversal") ll.printList()
So, you can see it is very easy to reverse a Linear Linked List using Python. You can understand the complete program of Linear Linked List here.