🚀 Learn BLE on Linux (BlueZ) – Programming Part 1
Hands-on Bluetooth Low Energy course. Special price: ₹399
Enroll Now on Udemy →Reverse Linked List Logic
Free C tutorial: understand what reversing a singly linked list really means, and why three pointers are the key, before you write a single line of code.
Reversing a linked list is one of the most asked questions in C interviews, and it appears in real firmware too: think of a stack of stored frames that must be replayed oldest first, or a packet chain built front-to-back that a driver wants to process in arrival order. In this lecture of our free C programming course we do not rush to code. We first build a clear picture of what must change, in which order, and why a naive attempt loses nodes. Master the picture, and the code in the next lecture becomes almost obvious. This lesson is part of our free embedded C course on C programming for embedded systems.
What You Will Learn
- What “reverse a linked list” means: reverse the arrows, not the values
- The four conditions a reversed list must satisfy
- Why you cannot flip arrows with only one or two pointers
- How the three pointers
prev,curandnextdivide the work - A complete hand trace on a four-node list
- Edge cases: empty list, one node, two nodes
Prerequisites
- The previous lectures on linked list insertion, deletion and traversal
- Pointer assignment and the arrow operator
->
What Does Reversing Mean?
Take a list that holds 8, 21, 34 and 55 in that order. After reversal it must read 55, 34, 21 and 8. There are two ways to get there. You could swap the stored values, which needs a second pass and extra copying and does not work if the nodes carry large payloads. The better way, and the one interviewers expect, is to rearrange the links: every node stays where it is in memory, but every next pointer is turned around to point at the node that used to come before it.
Same four nodes, arrows turned around
The four conditions of a reversed list
| # | Condition | In our example |
|---|---|---|
| 1 | The old first node becomes the last node, so its next must be NULL | Node 8 points to NULL |
| 2 | The old last node becomes the first, and head must point to it | head points to node 55 |
| 3 | Each middle node points to the node that used to precede it | 21 points to 8, 34 points to 21 |
| 4 | The old last node points to the node that used to be second last | 55 points to 34 |
Conditions 1 and 2 concern the ends and condition 3 and 4 concern the links. If your final list satisfies all four, you have reversed it correctly. Notice that nothing was allocated and nothing was freed: reversal moves no data and needs no extra memory except a few pointer variables. That is O(n) time and O(1) space.
Why One Pointer Is Not Enough
Suppose you stand on node 21 and want its arrow to point back at node 8. You write cur->next = prev. But the moment you do, the address of node 34 is gone: it lived only in cur->next. You can no longer reach the rest of the list, and nodes 34 and 55 are lost in memory. This is the heart of the problem.
cur->next, you must save its old value in another pointer. That saved pointer is the whole reason we need a third variable.
The Three-Pointer Technique
We use three pointers that always move together, like three people walking along the chain in single file.
| Pointer | Role | Starts as |
|---|---|---|
prev | The node already reversed, just behind the current one | NULL |
cur | The node whose arrow we are turning right now | head |
next | The saved rest of the list, still waiting | Set inside each pass |
Why does prev start as NULL? Because the first node must end up pointing to NULL, which is condition 1. By pointing the first node at prev on the first pass, we get that condition for free, with no special case.
The four moves in each pass
- Save:
next = cur->next, so the rest of the list is not lost. - Flip:
cur->next = prev, so the arrow now points backwards. - Advance prev:
prev = cur, so the processed part grows by one node. - Advance cur:
cur = next, so we move on to the saved node.
The order of these four moves is not a style choice; it is forced. Swap move 1 and move 2 and you lose the list. Swap moves 3 and 4 and you lose your position.
Hand Trace on Four Nodes
Let us follow the nodes 8, 21, 34 and 55. The notation shows the reversed part on the left and the untouched part on the right.
State after each pass
After pass 4, cur is NULL, so the loop ends. Now prev points to the old last node, which is the new first node. The final step is simply head = prev. That one assignment satisfies condition 2.
| Pass | next saved | Arrow flipped | prev after | cur after |
|---|---|---|---|---|
| 1 | 21 | 8 to NULL | 8 | 21 |
| 2 | 34 | 21 to 8 | 21 | 34 |
| 3 | 55 | 34 to 21 | 34 | 55 |
| 4 | NULL | 55 to 34 | 55 | NULL |
Edge Cases You Must Check
| List | What happens | Result |
|---|---|---|
| Empty (head is NULL) | The loop body never runs; prev is still NULL | head stays NULL |
| One node | One pass: node points to NULL, prev is that node | head unchanged in effect |
| Two nodes | Two passes; the arrows swap | Order swapped |
The best property of this technique is that these three cases need no special code. The same loop and the same final assignment handle them all.
Recursive reversal
You can also reverse recursively: reverse everything after the first node, then attach the first node at the end. It is elegant but uses stack space for every node, which can overflow on a small microcontroller with a long list. In embedded work, the iterative method is the safe choice.
Real-World Uses
- Stack to queue: items pushed at the front of a list come out newest first; reversing gives oldest first.
- Packet chains: a driver that prepends each received buffer to a list reverses it once before processing in arrival order.
- Undo history and log replay: reading events backwards, then restoring forward order.
- Interview preparation: reversal is the base for palindrome checks and merging problems.
Common Mistakes Before You Code
| Mistake | Consequence |
|---|---|
Flipping cur->next before saving it | Rest of the list is lost |
Starting prev as head | First node points to itself, creating an endless loop |
Forgetting to update head at the end | Head still points to the old first node, which is now the last |
| Reversing values instead of links | Slow, and fails for big payloads |
| Not testing the one-node list | Hidden bugs in off-by-one loops |
Best Practices
- Always draw the three pointers on paper with a four-node list before coding.
- Name the pointers by their role (
prev,cur,next), notp1,p2,p3; the names then explain the algorithm. - Take
struct node **headso the function can update the caller’s head. - Keep the loop to exactly four statements so you can verify each by eye.
Key Takeaways
- Reversing a list means turning each arrow around, not moving data.
- Three pointers are needed:
prev,curandnext. - Save, flip, advance prev, advance cur, in that order.
- When the loop ends,
previs the new head. - Time is O(n); extra space is O(1).
Conclusion
You now understand the logic of reversing a linked list well enough to explain it on a whiteboard: the goal, the four conditions, the danger of losing the tail, and the three-pointer cure. In the next lecture we turn this picture into working C code, test it on real data, and finish the chapter with a lab, a quiz and interview questions. Stay with this free C programming course to keep building solid embedded C programming skills.
Frequently Asked Questions
Why not simply swap the data of the first and last nodes, and so on?
On a singly linked list you cannot reach the last node backwards, so swapping pairs is awkward and slow. Rewiring links is simpler, and it works even when node payloads are large.
Why does prev start as NULL?
The old first node becomes the last node, and the last node must point to NULL. Starting prev as NULL makes the first pass do that automatically.
What is the time and space complexity?
Time is O(n) because each node is visited once. Space is O(1) because only three pointer variables are used.
Does reversal need malloc or free?
No. No nodes are created or destroyed, only their next pointers change.
Is the recursive version better?
It is shorter but uses stack space proportional to the list length. On microcontrollers the iterative version is safer.
Can a doubly linked list be reversed the same way?
Yes, but each node has two pointers to swap, and the head and tail must be exchanged.
Free Embedded C Course on EmbeddedPathashala
Next: write, run and test the reverse function, then take the chapter quiz.

2 Comments