Reverse a Singly Linked List

Reversing a Singly Linked List

Reversing a singly linked list involves changing the direction of the next pointers so that the last node becomes the head and the head becomes the last node. This operation requires traversing the list and updating the next references of each node.

---

Step-by-Step Process

Consider a singly linked list with the following structure before reversal:

Head -> 1 -> 2 -> 3 -> 4 -> None

We want to reverse the list so that it becomes:

Head -> 4 -> 3 -> 2 -> 1 -> None

Follow these steps to reverse the list:

1. Initialize Pointers: Start with three pointers: previous (prev) set to None, current (curr) set to the head, and next set to None.
2. Iterate Through the List: Traverse the list until the current pointer is None.
3. Reverse the Next Pointer: In each iteration, store the next node, update the current node's next pointer to point to the previous node, and then move the previous and current pointers one step forward.
4. Update the Head Pointer: After the loop, update the head pointer to point to the previous node (which will be the new head of the reversed list).

---

Python Program to Reverse a Singly Linked List

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

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def reverse(self):
        prev = None
        curr = self.head
        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        self.head = prev

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage:
linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
print("Linked list before reversal:")
linked_list.traverse()  # Output: 1 -> 2 -> 3 -> 4 -> None
linked_list.reverse()
print("Linked list after reversal:")
linked_list.traverse()  # Output: 4 -> 3 -> 2 -> 1 -> None

This Python program defines a singly linked list with methods for appending nodes, reversing the list, and traversing the list. The reverse method uses three pointers (prev, curr, and next) to reverse the direction of the next pointers, effectively reversing the list.