Python Program to Reverse a Linked List

A linked list is a data structure consisting of a sequence of nodes. Each node contains an element (or data) and a reference (or link) to the next node in the sequence. Singly linked lists have nodes that only point to the next node, creating a linear structure. Reversing a linked list involves changing the order of these pointers to flip the sequence of nodes.

Problem Statement

You are given a singly linked list, and you need to write a Python program to reverse the order of its elements.

Python Program to Reverse a Linked List

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def reverse(self):
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev
    
    def display(self):
        current = self.head
        while current:
            print(current.value, end=" -> ")
            current = current.next
        print("None")

# Create a linked list
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)

print("Original linked list:")
linked_list.display()

# Reverse the linked list
linked_list.reverse()

print("\nReversed linked list:")
linked_list.display()

How it Works

1. Node and LinkedList Classes:
   • The program starts by defining two classes: Node and LinkedList.
   • The Node class represents individual nodes in the linked list. Each node has a value and a reference to the next node in the list.
   • The LinkedList class manages the linked list. It has methods to append nodes to the end of the list, display the list, and most importantly, the reverse method to reverse the list.
2. Creating the Linked List:
   • An instance of the LinkedList class called linked_list is created.
   • Elements (values) are appended to the linked list using the append method. This method creates a new Node with the given value and appends it to the end of the list.
3. Displaying the Original Linked List:
   • The linked list is displayed using the display method. This method iterates through the linked list and prints the values of each node.
4. Reversing the Linked List:
   • The crucial part is the reverse method in the LinkedList class.
   • The method initializes two pointers, prev and current, both initially set to None and the head of the linked list, respectively.
   • It then iterates through the linked list:
     • The next_node variable is used to temporarily store the reference to the next node.
     • The current.next pointer is reversed to point to the previous node (prev).
     • The prev pointer is moved to the current node.
     • The current pointer is moved to the next node (stored in next_node).
   • The result of this process is a reversal of the pointers within the linked list.
5. Displaying the Reversed Linked List:
   • After reversing the linked list using the reverse method, the program displays the reversed linked list using the display method once again. Now the elements will be printed in reverse order.
6. Output:
   • The output demonstrates the original linked list and the reversed linked list.

Input/ Output