What is Reverse Linked List in C- C Programming Tutorials For Beginners

🚀 Learn BLE on Linux (BlueZ) – Programming Part 1

Hands-on Bluetooth Low Energy course. Special price: ₹399

Enroll Now on Udemy →
💬 Need help or career guidance? Ask us!Contact Us →

PREV_LEC | NEXT_LEC

Reverse Linked List in C

Three pointers, one loop, zero allocations: reverse a singly linked list in embedded C

To reverse a linked list in C you rewire the next pointer of every node so it points backwards, and you do it without allocating or copying a single node. This lecture of our free C programming course finishes the list-reversal topic from the structures chapter: we rebuild the idea from scratch, trace it by hand, then run a complete program on your own machine. Everything is written for embedded C programming, where memory is tight and allocation inside a routine is often not allowed.

What You Will Learn

  • The three-pointer technique used to reverse a linked list in C, and why each pointer exists
  • How to dry-run the loop on paper using a state table
  • How to handle an empty list and a one-node list without special cases
  • Two function signatures: returning the new head, and updating the head through a pointer to pointer
  • Why this operation is useful in interrupt-driven firmware, plus the races to avoid

Prerequisites

You should already be comfortable with self-referential structures, malloc() and free(), and traversing a singly linked list with a pointer. If not, revisit the earlier lectures of this free C tutorial chapter on linked lists first.

Why Reverse Linked List in C Matters in Firmware

A singly linked list only lets you walk forward. Insertion at the head is O(1), so firmware that collects data quickly (an interrupt handler queuing events, a driver chaining received buffers) naturally builds a list in newest-first order. When the main loop wants to process the data oldest-first, the cheapest fix is to reverse the list once instead of walking to the tail for every insertion.

SituationWhy reversal helps
ISR pushes events at the headMain loop reverses the batch once, then handles events in arrival order
Packet fragments chained as they arriveReverse to get fragments in transmit order before reassembly
Undo or history stackReverse to replay actions from oldest to newest
Interview questionIt tests pointer discipline and edge-case thinking in a few lines of code

The Three-Pointer Idea Behind Reverse Linked List in C

Reverse linked list in C is not about moving data. The node values stay exactly where they are in memory; only the arrows between them change direction. The danger is obvious: the moment you redirect one node, you lose the way forward unless you remembered it first. That is why we need three pointers.

PointerRoleStarts as
prevHead of the part that is already reversedNULL
currThe node whose link we are about to flipthe original head
savedThe untouched rest of the list, remembered before flippingset inside the loop

Each loop pass does four things, always in this order: remember the rest, flip the link, advance prev, advance curr. When curr becomes NULL, the loop is over and prev holds the old last node, which is the new head.

Before and after: only the links change
Beforenode 11→ node 22→ node 33→ node 44→ NULL
Afternode 44→ node 33→ node 22→ node 11→ NULL
State after each loop pass
Startprev = NULLcurr = 11
Pass 111 now points to NULLprev = 11curr = 22
Pass 222 now points to 11prev = 22curr = 33
Pass 333 now points to 22prev = 33curr = 44
Pass 444 now points to 33prev = 44curr = NULL, stop

Dry Run: Tracing the Loop by Hand

Always dry-run pointer code before you compile it. Here is the same trace as a table, using a four-node list holding 11, 22, 33 and 44.

PasssavedLink changeprev aftercurr after
12211.next = NULL1122
23322.next = 112233
34433.next = 223344
4NULL44.next = 3344NULL

This trace is the whole algorithm: reverse linked list in C is just this table repeated once per node. The function returns prev, which is node 44. Walking from there gives 44, 33, 22, 11, exactly the reversed list.

Edge Cases in Reverse Linked List in C: Empty and Single Node

Many textbook versions pre-load two or three pointers before the loop (for example reading head->next and head->next->next up front). That style needs an explicit guard, because a list with fewer than two or three nodes makes those reads invalid. The version in this lecture pre-loads nothing. It starts with prev = NULL and curr = head, so the cases fall out naturally:

ListWhat happensResult
Empty (head == NULL)Loop body never runsReturns NULL
One nodeOne pass: next becomes NULL, prev becomes that nodeReturns the same node
Many nodesOne pass per nodeReturns the old tail

Design tip

Prefer code where edge cases are handled by the loop condition instead of by extra if statements. Fewer branches means fewer places for a bug to hide.

Complete Program: Reverse Linked List in C

This is the complete reverse linked list in C demo. The program below builds a list of four event IDs, reverses it, prints both orders, and then checks the empty and one-node cases. It also frees every node, because an embedded engineer who forgets free() in a test program will forget it in firmware.

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

struct event {
    int id;
    struct event *next;
};

static struct event *push_back(struct event *head, int id)
{
    struct event *n = malloc(sizeof *n);
    if (!n) { perror("malloc"); exit(1); }
    n->id = id;
    n->next = NULL;
    if (!head) return n;
    struct event *t = head;
    while (t->next) t = t->next;
    t->next = n;
    return head;
}

/* returns the new head; works for 0, 1 and many nodes */
static struct event *reverse_list(struct event *head)
{
    struct event *prev = NULL;
    struct event *curr = head;

    while (curr) {
        struct event *saved = curr->next; /* remember the rest   */
        curr->next = prev;                /* flip this one link  */
        prev = curr;                      /* slide window ahead  */
        curr = saved;
    }
    return prev;                          /* old tail = new head */
}

static void show(const char *tag, const struct event *h)
{
    printf("%-8s:", tag);
    for (; h; h = h->next) printf(" %d", h->id);
    printf("\n");
}

int main(void)
{
    struct event *head = NULL;
    int ids[] = {11, 22, 33, 44};

    for (size_t i = 0; i < sizeof ids / sizeof ids[0]; i++)
        head = push_back(head, ids[i]);

    show("before", head);
    head = reverse_list(head);
    show("after", head);

    struct event *empty = reverse_list(NULL);
    printf("empty list stays %s\n", empty ? "broken" : "NULL");

    struct event *one = push_back(NULL, 99);
    one = reverse_list(one);
    show("single", one);

    while (head) { struct event *n = head->next; free(head); head = n; }
    free(one);
    return 0;
}

Build and run

gcc -Wall -Wextra -o rev rev.c
./rev

Expected output:

before  : 11 22 33 44
after   : 44 33 22 11
empty list stays NULL
single  : 99

How the code works

  • push_back() appends a node at the tail so we can build a known order for the demo.
  • reverse_list() is the heart of the lecture: save, flip, advance, advance. It returns prev because the old tail is now the head.
  • show() takes a const pointer because printing must never modify the list.
  • The caller reassigns head = reverse_list(head). Forgetting this assignment is the most common bug (see below).

Updating the Head Through a Pointer to Pointer

Returning the new head is simple, but some codebases prefer a function that fixes the caller’s head directly. That needs a pointer to the head pointer:

void reverse_in_place(struct event **head)
{
    struct event *prev = NULL, *curr = *head;

    while (curr) {
        struct event *saved = curr->next;
        curr->next = prev;
        prev = curr;
        curr = saved;
    }
    *head = prev;
}

Call it as reverse_in_place(&head);. Both forms do the same work. Avoid the old habit of keeping the list head in a global variable named start: a global hides state, makes the function impossible to reuse for a second list, and is not safe if two contexts touch it.

Iterative vs Recursive Reversal

PropertyIterativeRecursive
Extra memory3 pointers, O(1)One stack frame per node, O(n)
Risk on a small MCUNoneStack overflow on long lists
ReadabilityStraightforward once tracedShort, but harder to trace
Recommended for firmwareYesRarely

A list of 2000 nodes would need 2000 stack frames in the recursive version. On a Cortex-M with a 2 KB stack that is a crash, not a slowdown. Stay iterative.

Common Mistakes in Reverse Linked List in C Code

  1. Flipping before saving. If you write curr->next = prev before storing the old next pointer, the rest of the list is lost and leaks.
  2. Not using the return value. After reversal the caller’s old head is now the tail. Using it as the head silently shows a one-element list.
  3. Starting prev with garbage. It must start as NULL, otherwise the new tail points at random memory and later traversal never ends.
  4. Reversing while an interrupt edits the list. Detach the list atomically first, then reverse your private copy.
  5. Dereferencing head on an empty list. Always let the loop condition test curr before touching it.

Best Practices, Performance and Safety

  • Reverse linked list in C is O(n) time and O(1) space; no allocation means its run time is predictable, which suits real-time code.
  • Walk the list once afterwards in a debug build to assert that the node count did not change.
  • If an ISR produces the list, swap the head with NULL under a short critical section, then reverse outside the critical section to keep interrupt latency low.
  • Prefer clear names (prev, curr, saved) over p1, p2, p3. Readable pointer code is review-friendly code.
  • Test three lists every time: empty, one node, many nodes.

Key Takeaways

  • To reverse linked list in C, change links, never data.
  • The loop is always: save next, flip link, advance prev, advance curr.
  • Start with prev = NULL and the loop condition handles empty and single-node lists for free.
  • Return or store the new head, or the caller keeps a stale pointer.
  • In embedded systems stay iterative and protect lists shared with interrupts.

Conclusion

You now know how to reverse a linked list in C with three pointers (the standard reverse linked list in C technique), how to prove it by tracing a table, and where it appears in real firmware. This is a small function, but it trains habits that carry over to every pointer-heavy driver you will write: save before you overwrite, test the edge cases, and never lose the head. In the next lecture we leave linked lists behind and start a new data type, the union, which shares one block of memory between several members. Keep following this free embedded C course to continue the structure and union chapter.

Frequently Asked Questions

How do you reverse a linked list in C without extra memory?

Walk the list once with three pointers: prev (the already reversed part), curr (the node being flipped) and saved (the rest of the list). For every node you save its next pointer, point it back at prev, then slide the window forward. No new nodes are allocated, so the extra memory is just three pointers.

What is the time and space complexity of reversing a linked list?

Time is O(n) because each node is visited exactly once. Space is O(1) for the iterative version, since only a fixed number of pointers are used. A recursive version needs O(n) stack space, which matters on small microcontrollers.

Why does the function return the new head?

After reversal the old last node becomes the first node, so the head pointer of the caller is stale. Returning prev, or updating a struct node ** parameter, hands the caller the correct new head.

Does reversing a linked list work for an empty list or a single node?

Yes, when the loop starts from prev = NULL and curr = head. An empty list never enters the loop and returns NULL. A single node is flipped once, its next becomes NULL, and it is returned unchanged.

When would I reverse a linked list in embedded C programming?

A common case is an interrupt handler that pushes events at the head because that is O(1). The list then holds newest-first data, and the main loop reverses it once to process events oldest-first.

Is it safe to reverse a linked list that an ISR can modify?

Not without protection. Either detach the whole list atomically first (swap the head with NULL while interrupts are masked) and reverse your private copy, or disable interrupts for the whole operation.

Continue the Free C Programming Course

Next up: the C union, a data type that lets several members share the same memory, ideal for protocol messages and register views in embedded C programming.

PREV_LEC | NEXT_LEC

💬 Need help or career guidance? Ask us!Contact Us →

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

×

🚀 BLE on Linux (BlueZ)

Hands-on course. Only ₹399

Enroll Now →