Reversing a list in place in C

Three pointers walk the list once, flipping each link as they pass.

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

Node *reverse(Node *head) {
    Node *prev = NULL;
    while (head != NULL) {
        Node *next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

How it works

1. next is saved before the link is overwritten.
2. prev trails behind and becomes the new head.
3. No allocation happens at all.

Keywords and builtins used here

• NULL
• Node
• int
• return
• reverse
• struct
• typedef
• while

The run, in numbers

Lines

15

Characters to type

217

Tokens

67

Three-star pace

100 tpm

At the three-star pace of 100 tokens a minute, this run takes about 40 seconds.

Type this snippet

Step 3 of 5 in Lists & stacks, step 8 of 20 in Data structures & algorithms.

← Previous Next →