How can you reverse a linked list in Python?
FrankMl
Posted by FrankMl
Last Updated: August 25, 2024
linkedlist Python
Reversing a Linked List in Python
Reversing a linked list is a common interview question and a significant concept in data structures. A linked list consists of nodes, where each node contains a data value and a reference (or pointer) to the next node in the sequence. The challenge lies in changing the direction of the pointers such that the head of the list becomes the tail and vice versa.
Steps to Reverse a Linked List
1. Initialize Pointers: You'll need three pointers: prev, current, and next. The prev pointer is initially set to None since the new tail of the list will point to None. The current pointer will start at the head of the list. 2. Iterate Through the List: Loop through the linked list, and for each node: - Store the next node by assigning current.next to next. - Reverse the current node's pointer by setting current.next to prev. - Move the prev and current pointers one step ahead. 3. Update the Head: Once the loop completes, update the head of the linked list to be prev, which will be the new head.
Implementation
Here's a Python implementation of the above logic: 
class Node:
    """Class to represent a node in a linked list."""
    def init(self, value):
        self.value = value
        self.next = None

class LinkedList:
    """Class to represent a linked list."""
    def init(self):
        self.head = None

    def append(self, value):
        """Add a node with the given value to the end of the list."""
        if not self.head:
            self.head = Node(value)
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(value)

    def reverse(self):
        """Reverse the linked list."""
        prev = None
        current = self.head
        while current:
            next_node = current.next   # Store the next node
            current.next = prev        # Reverse the pointer
            prev = current             # Move prev and current one step forward
            current = next_node
        self.head = prev              # Update head to the new front of the list

    def print_list(self):
        """Print the linked list."""
        current = self.head
        while current:
            print(current.value, end=" -> ")
            current = current.next
        print("None")


# Example Usage
if name == "main":
    ll = LinkedList()
    ll.append(1)
    ll.append(2)
    ll.append(3)
    ll.append(4)

    print("Original Linked List:")
    ll.print_list()

    ll.reverse()

    print("Reversed Linked List:")
    ll.print_list()
Explanation of the Code
- Node Class: Represents an individual node in the linked list. - LinkedList Class: Contains methods to append values, reverse the linked list, and print the list for visualization. - Reverse Method: Implements the pointer-reversal algorithm described above. - Print List Method: This method outputs the values in the linked list in order, demonstrating the structure before and after reversal.
Conclusion
Reversing a linked list is a fundamental operation that showcases the use of pointers effectively. The provided code not only achieves this but also demonstrates how to manipulate linked lists in Python for practical applications. Understanding this technique can significantly enhance proficiency in data structure manipulation.
Default Image