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.java

public class Basic {
    static class Node {
        int value;
        Node next;
        Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Node n5 = new Node(5, null);
        Node n4 = new Node(4, n5);
        Node n3 = new Node(3, n4);
        Node n2 = new Node(2, n3);
        Node head = new Node(1, n2);

        Node prev = null;
        Node cursor = head;
        while (cursor != null) {
            Node next = cursor.next;
            cursor.next = prev;
            prev = cursor;
            cursor = next;
        }
        head = prev;
    }
}

Complexity

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

Implementation notes

Java: same three-pointer pattern as the other languages. 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`).