Linked Structures

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

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;
}

The three-pointer loop saves the forward link, flips one next pointer, then advances prev and cursor.

Step 1 - Save the first forward link

prev starts at null, cursor is node(1), and nxt saves node(2).

Initial 1 -> 2 -> 3 -> 4 -> 5 chain with prev, cursor, and nxt named.prevcursornxtnullnode(1)node(2)node(3)node(4)node(5)

Step 2 - Flip node(1)

Set node(1).next to prev, making the reversed prefix 1 -> null.

After the first flip, prev points at node(1) and cursor advances to node(2).prevcursornode(1)nullnode(2)node(3)node(4)node(5)

Step 3 - Reversed prefix reaches 3

After three flips, the prefix is 3 -> 2 -> 1 -> null and cursor is node(4).

Middle of the reverse: prefix 3 -> 2 -> 1, suffix 4 -> 5.prevcursornode(3)node(2)node(1)nullnode(4)node(5)

Step 4 - Done

When cursor reaches null, prev is the new head: 5 -> 4 -> 3 -> 2 -> 1 -> null.

Final reversed list.headnode(5)node(4)node(3)node(2)node(1)null

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`).