Reverse Linked List

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

Constraints:

• The number of nodes is in the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed iteratively or recursively. Could you implement both?

Brute Force

Copy all the values into an array, then write them back in reverse order.

1. Walk through the list and push every value into an array.
2. Walk through the list a second time.
3. Put the last value of the array into the first node, the second last into the second node, and so on.

This works, but it uses extra memory for the array. It also changes the values, not the links.

class Solution {
    public:
    ListNode* reverseList(ListNode* head) {
        vector<int> values;
        ListNode* curr = head;

        while (curr != nullptr) {
            values.push_back(curr->val);
            curr = curr->next;
        }

        curr = head;
        int index = values.size() - 1;

        while (curr != nullptr) {
            curr->val = values[index];
            index--;
            curr = curr->next;
        }

        return head;
    }
};

• Time: O(n). Two passes over the list.
• Space: O(n). The array holds every value.

Optimal Approach: Three Pointers (Iterative)

Instead of moving values, flip the arrows. Each node's next should point to the node before it, not after it.

We use three pointers:

• prev: the node behind curr. It starts as null, because the new tail points to nothing.
• curr: the node we are fixing right now. It starts at head.
• nextNode: a saved copy of curr.next, so we do not lose the rest of the list.

Steps:

1. Set prev = null and curr = head.
2. Loop while curr is not null.
3. Save the next node: nextNode = curr.next.
4. Flip the arrow: curr.next = prev.
5. Move forward: prev = curr, then curr = nextNode.
6. When the loop ends, curr is null and prev is the new head. Return prev.

class Solution {
    public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;

        while (curr != nullptr) {
            ListNode* nextNode = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextNode;
        }

        return prev;
    }
};

Dry Run

Take head = [1,2,3].

1Start: prev = null, curr = 1
2 
3Step | curr | nextNode (saved) | flip arrow     | prev after | curr after | Reversed part
4-----|------|------------------|----------------|------------|------------|--------------
5  1  |  1   |  2               | 1.next = null  |  1         |  2         | null <- 1
6  2  |  2   |  3               | 2.next = 1     |  2         |  3         | null <- 1 <- 2
7  3  |  3   |  null            | 3.next = 2     |  3         |  null      | null <- 1 <- 2 <- 3
8 
9curr = null, so the loop stops.
10 
11Return prev = 3, so the list is: 3 -> 2 -> 1

Why Does This Work?

Imagine people standing in a line, each one holding the hand of the person in front. You want everyone to turn around so the line runs the other way.

Small example first. The list is 1 -> 2.

• Person 1 lets go of person 2 and holds null instead. Now it is null <- 1.
• Person 2 lets go of nothing and holds person 1. Now it is null <- 1 <- 2.
• Person 2 is now at the front. The list is 2 -> 1.

Here is the general rule. In every loop we do the same three things:

• Remember who is next (nextNode).
• Turn the current node to face backward (curr.next = prev).
• Step forward (prev = curr, curr = nextNode).

Why save nextNode first? Once we write curr.next = prev, the link to the rest of the list is gone. If we did not save it, we would lose every node after curr.

Why does prev start as null? The old head becomes the new tail, and a tail points to nothing.

Why return prev and not curr? At the end curr has walked off the list and is null. prev is the last node we fixed, which is the new head. It also works for an empty list, because prev stays null.

Why This Is Better Than Brute Force

• The brute force stores all values in an array, so it uses O(n) extra memory. The three pointers use O(1) extra memory.
• It is one pass instead of two.
• It re-links the nodes instead of copying values around, which is what "reverse a linked list" really means.
• Time stays O(n), so we save memory without losing speed.

Complexity

How to Explain It in an Interview