Reverse Linked List — Editorial

Opening the reading…

Intuitionwhy each link changes direction exactly once

A singly linked list gives you only one direction to follow: from a node to its next node. Reversing the list means changing every link so it points to the node you just came from. While you change one link, you must still remember the original next node, because after the change the original forward path is no longer reachable from the current node.

Keep prev as the already reversed part and curr as the first node not yet processed. Save curr->next, point curr back to prev, then move both pointers forward. When curr becomes null, every link has been reversed and prev points to the new head. The original head has become the final node, so its next pointer is already null.

Approach

Set prev to null and curr to head, because the first node in the reversed list must point to null and curr must begin at the original head.

Save curr->next in next before changing any link, because curr->next is the only reference to the rest of the original list.

Set curr->next to prev, because this reverses the current node's link and attaches it to the already reversed prefix.

Move prev to curr, because the reversed prefix now starts at the node you just processed.

Move curr to next, because next is the first node that still needs its link reversed.

Repeat while curr is not null, because stopping at null means every original node has been processed without dereferencing an absent node.

Return prev, because curr is null at the end and prev is the node at the front of the fully reversed list.

Complexityeach node is changed once

MEASURE	BOUND	WHY
Time	O(n)	Each node becomes curr once, and each iteration performs a constant number of pointer reads and writes. The loop advances curr to the next unprocessed node, so no node is processed twice.
Space	O(1) extra space	The algorithm stores only prev, curr, and next; the reversed list is required output and is excluded from the working-memory bound. The bound remains constant even for the worst-shaped input, a list containing all n nodes in one chain.

Here, n is the number of nodes in the list.

Annotated solutionC++ · iterative · constant extra space

CPPReverse each link in one pass while keeping the remaining suffix reachable.

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

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

        return prev;
    }
};

The order of the four statements inside the loop is the solution's invariant made executable. The assignment to next must happen before curr->next changes; after that change, curr no longer points forward. The return value is prev rather than head because the original head moves to the tail, while the original tail becomes the new entry point.

The recursive alternativea different arrangement that spends stack space

Recursion can reverse the suffix first, then attach the current node after the suffix's original tail. For a node head, reverseList(head->next) returns the new head of the reversed suffix. The old second node is now at that suffix's tail, so setting head->next->next to head puts head after it, and setting head->next to null prevents a cycle.

CPPRecursively reverse the suffix, then place the current node at its end.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};