Python Program to Reverse a Linear Linked List

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 .

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

step 2
Step 3
step 4
Linear Linked List

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

Linear Linked List revresal

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

Output

Output of Python Program to Reverse a Linear Linked List

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.

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *