Python: Reverse a Linked List

1. Introduction

Reversing a linked list is a foundational problem in data structures. The process involves changing the next pointers of every node in the linked list to point to its previous node. It's an essential concept, often used in coding interviews and algorithm development.

2. Program Overview

The Python program provided will:

1. Define a Node class for creating linked list nodes.

2. Define a LinkedList class that will have methods for adding elements and reversing the linked list.

3. Implement the reversing technique by iterative method.

3. Code Program

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

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        """Add a new node at the end of the linked list."""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        """Print all elements of the linked list."""
        cur_node = self.head
        while cur_node:
            print(cur_node.data, end=" -> ")
            cur_node = cur_node.next
        print("None")

    def reverse(self):
        """Reverse the linked list."""
        prev = None
        current = self.head
        while current:
            nxt = current.next
            current.next = prev
            prev = current
            current = nxt
        self.head = prev

# Sample test
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.append(4)
print("Original Linked List:")
llist.print_list()

llist.reverse()
print("\nReversed Linked List:")
llist.print_list()

Output:

Original Linked List:
1 -> 2 -> 3 -> 4 -> None

Reversed Linked List:
4 -> 3 -> 2 -> 1 -> None

4. Step By Step Explanation

1. We start by defining a Node class, which is a basic building block of the linked list.

2. The LinkedList class has an append method to add new nodes to the list and a print_list method to display the list.

3. The reverse method inside the LinkedList class is where the magic happens. Here's a step-by-step breakdown of the reversing process:

• We initialize three pointers: prev, current, and nxt. Initially, prev is set to None because the last node in the reversed list will point to None.
• We traverse the linked list using the current pointer.
• During each iteration, we first save the next node using the nxt pointer.
• We then change the next pointer of the current node to point to prev.
• We move the prev and current pointers one step forward.
• Once the traversal is complete, we set the head of the linked list to the prev pointer, effectively reversing the list.