🚀 Learn BLE on Linux (BlueZ) – Programming Part 1
Hands-on Bluetooth Low Energy course. Special price: ₹399
Enroll Now on Udemy →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.
| Situation | Why reversal helps |
|---|---|
| ISR pushes events at the head | Main loop reverses the batch once, then handles events in arrival order |
| Packet fragments chained as they arrive | Reverse to get fragments in transmit order before reassembly |
| Undo or history stack | Reverse to replay actions from oldest to newest |
| Interview question | It 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.
| Pointer | Role | Starts as |
|---|---|---|
prev | Head of the part that is already reversed | NULL |
curr | The node whose link we are about to flip | the original head |
saved | The untouched rest of the list, remembered before flipping | set 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.
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.
| Pass | saved | Link change | prev after | curr after |
|---|---|---|---|---|
| 1 | 22 | 11.next = NULL | 11 | 22 |
| 2 | 33 | 22.next = 11 | 22 | 33 |
| 3 | 44 | 33.next = 22 | 33 | 44 |
| 4 | NULL | 44.next = 33 | 44 | NULL |
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:
| List | What happens | Result |
|---|---|---|
Empty (head == NULL) | Loop body never runs | Returns NULL |
| One node | One pass: next becomes NULL, prev becomes that node | Returns the same node |
| Many nodes | One pass per node | Returns 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 returnsprevbecause the old tail is now the head.show()takes aconstpointer 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
| Property | Iterative | Recursive |
|---|---|---|
| Extra memory | 3 pointers, O(1) | One stack frame per node, O(n) |
| Risk on a small MCU | None | Stack overflow on long lists |
| Readability | Straightforward once traced | Short, but harder to trace |
| Recommended for firmware | Yes | Rarely |
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
- Flipping before saving. If you write
curr->next = prevbefore storing the old next pointer, the rest of the list is lost and leaks. - 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.
- Starting prev with garbage. It must start as
NULL, otherwise the new tail points at random memory and later traversal never ends. - Reversing while an interrupt edits the list. Detach the list atomically first, then reverse your private copy.
- Dereferencing head on an empty list. Always let the loop condition test
currbefore 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
NULLunder a short critical section, then reverse outside the critical section to keep interrupt latency low. - Prefer clear names (
prev,curr,saved) overp1,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 = NULLand 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.

2 Comments