Step 5 of 6

Reverse a linked list

Reversing a linked list is a famous interview question because it tests whether you can manipulate pointers without losing track of anything. The goal: flip every next arrow to point backwards, in one pass, without allocating new nodes.

Three pointers

• prev: the part already reversed (starts as NULL, the new end).
• cur: the node being flipped (starts at the head).
• next: saved before flipping, so the rest of the list isn't lost.

Each step:

1. Save next = cur->next.
2. Flip: cur->next = prev.
3. Move forward: prev = cur, then cur = next.

When cur becomes NULL, prev is the new head.

The Watch it run link below shows exactly this: watch the heap arrows turn around one at a time. Here's the same three-pointer walk used for a different job, removing every node with a given value (it needs to remember the previous node to relink around the removed one):

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

struct Node {
    int value;
    struct Node *next;
};

struct Node *remove_all(struct Node *head, int target) {
    struct Node *prev = NULL, *cur = head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        if (cur->value == target) {
            if (prev == NULL) head = next;
            else prev->next = next;
            free(cur);
        } else {
            prev = cur;
        }
        cur = next;
    }
    return head;
}

int main(void) {
    int vals[] = {3, 1, 3, 2};
    struct Node *head = NULL;
    for (int i = 3; i >= 0; i--) {
        struct Node *n = malloc(sizeof *n);
        if (!n) return 1;
        n->value = vals[i];
        n->next = head;
        head = n;
    }
    head = remove_all(head, 3);
    for (struct Node *p = head; p; p = p->next) printf("%d ", p->value);
    printf("\n");
    while (head) { struct Node *n = head->next; free(head); head = n; }
    return 0;
}

1 2 

Draw a small list on paper and trace your reverse before coding. Check the empty list and a one-node list too.

Your turn: write struct Node *reverse(struct Node *head) that returns the new head.

Previous: Free the whole list Next: A stack on an array