Reversing a Linked List

Reversing a linked list is a fundamental operation in computer science that transforms the order of elements from head-to-tail to tail-to-head. This process is crucial for various algorithms and data structures, requiring careful manipulation of pointers to ensure no data is lost.

How it Works

The core challenge in reversing a linked list is to reorient each node's `next` pointer to its preceding node without losing access to the rest of the list. This is achieved iteratively using three pointers: `prev`, `curr`, and `next`.

Initially, `prev` is set to `null` (as the new head will point to nothing), and `curr` points to the original head of the list. The `next` pointer is a temporary placeholder that will store the link to the subsequent node before `curr`'s `next` pointer is changed.

The Iteration Process

For each node, the following steps are performed:

1. Save the next node: Before modifying `curr.next`, store the reference to `curr.next` in the `next` pointer. This ensures you don't lose the rest of the list when `curr.next` is rewired. 2. Reverse the link: Point `curr.next` to `prev`. This effectively reverses the direction of the current node's pointer. 3. Advance pointers: Move `prev` to `curr`, and `curr` to `next`. This shifts the window of operation one node forward, preparing for the next iteration.

This process continues until `curr` becomes `null`, indicating that all nodes have been processed. At this point, `prev` will be pointing to the new head of the reversed list.

function reverseLinkedList(head):
    prev = null
    curr = head
    while curr is not null:
        next_node = curr.next  // Step 1: Save next
        curr.next = prev       // Step 2: Reverse link
        prev = curr            // Step 3a: Advance prev
        curr = next_node       // Step 3b: Advance curr
    return prev                // prev is the new head

Key Takeaways

• Reversing a linked list involves changing the `next` pointer of each node.
• Three pointers (`prev`, `curr`, `next`) are essential to manage the reversal without losing track of nodes.
• Always save the `next` node *before* modifying the current node's `next` pointer.
• The `prev` pointer ultimately becomes the new head of the reversed list.
• The algorithm processes each node once, resulting in O(n) time complexity and O(1) space complexity.