Reverse a Linked List

Concept

“Reverse a Linked List.”
It is a running joke in the software industry that this single question dictates whether you get hired at Google.

Problem: Given the head of a singly linked list, reverse the list, and return the reversed list.
Input: 1 -> 2 -> 3 -> 4 -> null
Output: 4 -> 3 -> 2 -> 1 -> null

The Iterative Approach (The Best Way)

You cannot solve this by creating a new array. You must do it in-place ($O(1)$ extra space) by carefully rewiring the next pointers backwards.

To do this without losing the rest of the list, you need exactly Three Pointers:

1. prev: Initially null. This will eventually become our new Head.
2. current: The node we are currently looking at.
3. next_temp: A temporary lifeline. If we break current.next to point backwards, we physically lose the bridge to the rest of the list. We must save the bridge in next_temp before breaking it.

Mental Model

1. prev = null, current = 1
2. Save the bridge: next_temp = 2
3. Rewire backwards: current.next = prev (Node 1 now points to null).
4. March forward: prev = current (prev is now 1), current = next_temp (current is now 2).
5. Repeat for Node 2. It will point backwards to prev (1).

Implementation

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}

// Time Complexity: O(N)
// Space Complexity: O(1)
function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let current: ListNode | null = head;

    while (current !== null) {
        // 1. Save the bridge to the future
        let nextTemp = current.next;
        
        // 2. Reverse the pointer backwards
        current.next = prev;
        
        // 3. March both pointers forward by one step
        prev = current;
        current = nextTemp;
    }

    // When current hits null, the loop ends. 
    // 'prev' is sitting exactly on the very last node (the new Head!)
    return prev;
}

The Recursive Approach

Interviewers will often ask: “Great, now do it recursively.”

Recursion achieves the exact same pointer rewiring, but instead of using a while loop, it relies on the Call Stack to travel to the very end of the list, and then wire the pointers backwards as the stack unwinds.

// Time Complexity: O(N)
// Space Complexity: O(N) (Due to the Call Stack!)
function reverseListRecursive(head: ListNode | null): ListNode | null {
    // Base Case: Empty list, or we reached the very last node
    if (head === null || head.next === null) {
        return head; // This last node will be passed all the way up as the new Head
    }

    // Traverse all the way to the end
    const newHead = reverseListRecursive(head.next);

    // As the stack unwinds, we are sitting at a node (e.g., 3). 
    // head.next is 4. We want 4 to point back to 3.
    head.next.next = head;
    
    // Sever the original forward pointer to prevent a cycle
    head.next = null;

    // Keep bubbling the true 'newHead' up the stack
    return newHead;
}

Interview Questions

Q: Between the Iterative approach and the Recursive approach, which one would you deploy to a production environment, and why?
A: I would absolutely deploy the Iterative approach.
The Iterative approach uses exactly three variables in memory, giving it $O(1)$ Space Complexity.
The Recursive approach pushes a new frame to the Call Stack for every single node. If the Linked List has 50,000 nodes, the recursion will hit the maximum call stack size and throw a Stack Overflow Error, crashing the entire application. The Recursive approach is an elegant academic exercise, but it is too dangerous (and consumes $O(N)$ space) for production systems holding massive datasets.