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

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int value;
    struct ListNode *next;
} ListNode;

static ListNode *make_node(int v, ListNode *next) {
    ListNode *n = malloc(sizeof(ListNode));
    n->value = v;
    n->next = next;
    return n;
}

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

    ListNode *prev = NULL;
    ListNode *cursor = head;
    while (cursor != NULL) {
        ListNode *next = cursor->next;
        cursor->next = prev;
        prev = cursor;
        cursor = next;
    }
    head = prev;
    ListNode *cur = head;
    while (cur != NULL) {
        printf("%d -> ", cur->value);
        cur = cur->next;
    }
    printf("null\n");
    cur = head;
    while (cur != NULL) {
        ListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    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 NULL 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 `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`).