Linked Structures

Reverse a Singly Linked List

Walk the list with three references: 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.ts 
class ListNode {
    value: number;
    next: ListNode | null;
    constructor(value: number, next: ListNode | null) {
        this.value = value;
        this.next = next;
    }
}

const n5: ListNode = new ListNode(5, null);
const n4: ListNode = new ListNode(4, n5);
const n3: ListNode = new ListNode(3, n4);
const n2: ListNode = new ListNode(2, n3);
let head: ListNode | null = new ListNode(1, n2);

let prev: ListNode | null = null;
let cursor: ListNode | null = head;
while (cursor !== null) {
    const next: ListNode | null = cursor.next;
    cursor.next = prev;
    prev = cursor;
    cursor = next;
}
head = prev;

Complexity

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

Implementation notes

  • TypeScript: same three-pointer pattern as the other languages. Each pointer carries the ListNode | null union type so the end-of-list null is honest.
  • 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.
three pointers `prev` starts `null`, `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`).