Introduction & Problem Explanation

The Reverse a Linked List problem is a core data structures challenge. We are given the head of a singly linked list, and we need to reverse the list so that the nodes point in the opposite direction, returning the new head of the reversed list.

For example, if the input is 1 -> 2 -> 3 -> 4 -> null, the reversed list should be 4 -> 3 -> 2 -> 1 -> null. The constraint is that we should perform this operation in-place using constant auxiliary space O(1), which means we must carefully manipulate the existing references.

Illustration of reversing a singly linked list in Java
Real-World Analogy: The Reversing Conga Line

Imagine a conga line where each person has their hands on the shoulders of the person in front of them, pointing to the direction of travel. To reverse the direction of the line without making anyone move to a different position, each person must turn around and place their hands on the shoulders of the person who was previously *behind* them. In code, the "shoulders" are the next pointer references of the list nodes. Each node must swap its forward link to point to its predecessor.

The Algorithmic Approach

1. Iterative Pointer Reordering (O(n) Time, O(1) Space)

We traverse the list once. For each node, we redirect its next pointer to the previous node (prev). To avoid losing track of the rest of the list when we break the link, we must save the next node in a temporary variable (nextNode) before rewriting the pointer. We use three pointers:

  • prev: Keeps track of the node that will become the new next node (starts as null).
  • curr: The current node we are processing (starts as head).
  • nextNode: A temporary placeholder to store curr.next.
This runs in linear O(n) time using only constant O(1) memory.

Step-by-Step Execution Walkthrough

Let's trace the iterative reversal on the list 1 -> 2 -> 3 -> null:

  1. Step 1 (Initialization):
    • prev = null
    • curr = 1
  2. Step 2 (First Iteration, Node 1):
    • Save the next node: nextNode = curr.next (which is node 2).
    • Reverse the link: curr.next = prev (which is null). Now, node 1 points to null: 1 -> null.
    • Move pointers forward: prev = curr (1), curr = nextNode (2).
  3. Step 3 (Second Iteration, Node 2):
    • Save the next node: nextNode = curr.next (which is node 3).
    • Reverse the link: curr.next = prev (which is node 1). Now, node 2 points to node 1: 2 -> 1 -> null.
    • Move pointers forward: prev = curr (2), curr = nextNode (3).
  4. Step 4 (Third Iteration, Node 3):
    • Save the next node: nextNode = curr.next (which is null).
    • Reverse the link: curr.next = prev (which is node 2). Now, node 3 points to node 2: 3 -> 2 -> 1 -> null.
    • Move pointers forward: prev = curr (3), curr = nextNode (null).
  5. Step 5 (Completion): Since curr is now null, the loop ends. We return prev, which is node 3, representing the new head of the reversed list: 3 -> 2 -> 1 -> null.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

  • ListNode nextNode = curr.next;: Keeps a reference to the remaining chain before we break the forward link.
  • curr.next = prev;: The actual reversal step, redirecting the arrow backward to the node we just visited.
  • prev = curr; curr = nextNode;: Steps the pointers forward by one node to continue the traversal.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

public class ReverseLinkedList {

    public static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) { this.val = val; }
    }

    // Optimized - Iterative O(n)
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode nextNode = head.next;
            head.next = prev;
            prev = head;
            head = nextNode;
        }
        return prev;
    }

    public static void main(String[] args) {
        ReverseLinkedList solver = new ReverseLinkedList();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);

        System.out.println("--- Reverse Linked List Demonstration ---");
        System.out.print("Original List: ");
        printList(head);

        ListNode reversed = solver.reverseList(head);
        System.out.print("Reversed List: ");
        printList(reversed);
    }

    private static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + (curr.next != null ? " -> " : ""));
            curr = curr.next;
        }
        System.out.println();
    }
}

Conclusion

Solving the Reverse a Linked List problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.