Reverse a Singly Linked List

Walk the list with three pointers: prev, cursor, and next. Each iteration saves cursor->next, re-points cursor->next backward to prev, then advances prev = cursor; cursor = next.

Algorithm

Canonical input 1 -> 2 -> 3 -> 4 -> 5 -> null reverses to 5 -> 4 -> 3 -> 2 -> 1 -> null after five rewire frames.

Basic Implementation

basic.cpp

#include <iostream>

struct ListNode {
    int value;
    ListNode* next;
    ListNode(int v, ListNode* n) : value(v), next(n) {}
};

int main() {
    ListNode* n5 = new ListNode(5, nullptr);
    ListNode* n4 = new ListNode(4, n5);
    ListNode* n3 = new ListNode(3, n4);
    ListNode* n2 = new ListNode(2, n3);
    ListNode* head = new ListNode(1, n2);

    ListNode* prev = nullptr;
    ListNode* cursor = head;
    while (cursor != nullptr) {
        ListNode* next = cursor->next;
        cursor->next = prev;
        prev = cursor;
        cursor = next;
    }
    head = prev;
    ListNode* cur = head;
    while (cur != nullptr) {
        std::cout << cur->value << " -> ";
        cur = cur->next;
    }
    std::cout << "null" << std::endl;
    cur = head;
    while (cur != nullptr) {
        ListNode* n = cur->next;
        delete cur;
        cur = n;
    }
    return 0;
}

Complexity

Time: O(n)
Space: O(1)

Implementation notes

C++: same three-pointer pattern as the other languages. Each pointer is a raw ListNode*, and nullptr represents end-of-list honestly.
Reverse in place and reassign head = prev at the end.
The replay shows all three pointers each frame and a distinct rewire frame between save and advance, with node(<value>) labels instead of raw addresses.

three pointers `prev` starts `nullptr`, `cursor` starts at `head`, `next` is the saved forward link.

rewire The rewire frame flips `cursor->next` from forward (toward `next`) to backward (toward `prev`).