Reverse a Linked List

Reversing a linked list is one of those fundamental operations that underpins many real-world tasks—reordering a playlist, undo history, or rolling back actions. In interviews, it’s a go-to warm-up that tests your understanding of pointers and in-place list manipulation.

Problem Statement

Given the head of a singly linked list, reverse the list in place and return the new head of the reversed list.

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// Signature presented in a technical interview
public ListNode reverseList(ListNode head);

1. Clarify Requirements Before Jumping Into Code

Let me confirm a few details:

• The list is singly linked, not doubly.

• I need to reverse the next pointers, not just values.

• In-place means O(1) extra space.

• Return the new head; original head’s next should become null.

• Input head may be null or a single node.

2. Identify the Category of the Question

This is a linked list manipulation problem. Common linked-list patterns include:

• Two-pointer (fast/slow) for cycle detection or middle finding

• In-place pointer reversal for flipping or rotating

• Recursion for backtracking on nodes

• Dummy head technique for insertion/removal

• Hashing for random pointer or intersection problems

Reversing fits the in-place pointer-manipulation pattern.

3. Consider a Brute-Force Approach to Understand the Problem

A naive idea: copy node values into an array, reverse the array, then write them back into the list.

• Time: O(n) for array build + O(n) for writeback = O(n)

• Space: O(n) extra array

• Drawback: Uses O(n) space, violates in-place requirement

Still, this confirms the reversal logic: last element becomes first, etc.

4. Brainstorm More Solutions

I need O(1) extra space. Two main ways come to mind:

1. Recursive reversal: Reverse the rest of the list, then set head.next.next = head and head.next = null. That uses call stack O(n).

2. Iterative three-pointer: Maintain

   • prev for the node already reversed,

   • curr for current node to process,

   • nextTemp to hold curr.next before changing pointers.Move through the list, rewiring one pointer at a time.

If I didn’t recall details, I’d think through walking the list: at each node I want to flip its arrow to point back. But I need to remember where it came from (prev) and where to go next (nextTemp). That leads naturally to the three-pointer approach.

5. Discuss Trade-Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Array + rewrite	O(n)	O(n)	Easy to implement	Uses extra O(n) space
Recursive reversal	O(n)	O(n) stack	Elegant, few lines of code	Risk of stack overflow on large n
Iterative three-pointer	O(n)	O(1)	In-place, constant extra space	Slightly more pointer management

Iterative three-pointer is optimal for in-place reversal with minimal risk.

6. Write Pseudocode to Structure Your Thoughts

function reverseList(head):
  prev = null
  curr = head
  while curr != null:
    nextTemp = curr.next
    curr.next = prev
    prev = curr
    curr = nextTemp
  return prev  // new head

7. Consider Edge Cases

• Empty list (head = null) → return null

• Single node → return the same node, next stays null

• Two nodes → pointers swap correctly

• Already reversed list → algorithm still applies

• Very long list → no recursion, so no stack overflow

8. Write Full Code Syntax

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        return prev;
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    // Helper to build and print lists omitted for brevity

    // Test 1: empty list
    assert sol.reverseList(null) == null;

    // Test 2: single node
    ListNode one = new ListNode(1);
    ListNode res1 = sol.reverseList(one);
    assert res1 == one && res1.next == null;

    // Test 3: two nodes
    ListNode head2 = new ListNode(1);
    head2.next = new ListNode(2);
    ListNode res2 = sol.reverseList(head2);
    assert res2.val == 2 && res2.next.val == 1 && res2.next.next == null;

    // Test 4: multiple nodes
    ListNode head3 = new ListNode(1);
    head3.next = new ListNode(2);
    head3.next.next = new ListNode(3);
    ListNode res3 = sol.reverseList(head3);
    assert res3.val == 3 && res3.next.val == 2 && res3.next.next.val == 1;

    // Test 5: longer list
    ListNode head5 = new ListNode(5);
    ListNode curr = head5;
    for (int i = 6; i <= 9; i++) {
        curr.next = new ListNode(i);
        curr = curr.next;
    }
    ListNode res5 = sol.reverseList(head5);
    int expected = 9;
    curr = res5;
    while (curr != null) {
        assert curr.val == expected--;
        curr = curr.next;
    }

    System.out.println("All tests passed!");
}

10. Key Lessons to Remember for Future Questions

• Pointer reversal pattern: track prev, curr, and next to rewire links in place.

• Start simple: brute-force or recursion clarifies correctness, then optimize space.

• Pseudocode first: writing the three-pointer loop in abstract form prevents errors.

• Edge-case checks: empty and single-node lists should be first smoke tests.

• Iterative vs. recursive: choose iterative for large inputs to avoid stack overflow.