What is Reverse Linked List Logic- Best C Language Course 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 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, cur and next divide 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

Originalhead→8→21→34→55→NULL
Reversedhead→55→34→21→8→NULL

The four conditions of a reversed list

#ConditionIn our example
1The old first node becomes the last node, so its next must be NULLNode 8 points to NULL
2The old last node becomes the first, and head must point to ithead points to node 55
3Each middle node points to the node that used to precede it21 points to 8, 34 points to 21
4The old last node points to the node that used to be second last55 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.

Do not flip first and think later. Before you overwrite 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.

PointerRoleStarts as
prevThe node already reversed, just behind the current oneNULL
curThe node whose arrow we are turning right nowhead
nextThe saved rest of the list, still waitingSet 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

  1. Save: next = cur->next, so the rest of the list is not lost.
  2. Flip: cur->next = prev, so the arrow now points backwards.
  3. Advance prev: prev = cur, so the processed part grows by one node.
  4. 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

Startprev = NULLcur = 8→21→34→55
Pass 18 → NULLprev = 8cur = 21→34→55
Pass 221 → 8 → NULLprev = 21cur = 34→55
Pass 334 → 21 → 8 → NULLprev = 34cur = 55
Pass 455 → 34 → 21 → 8 → NULLprev = 55cur = NULL

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.

Passnext savedArrow flippedprev aftercur after
1218 to NULL821
23421 to 82134
35534 to 213455
4NULL55 to 3455NULL

Edge Cases You Must Check

ListWhat happensResult
Empty (head is NULL)The loop body never runs; prev is still NULLhead stays NULL
One nodeOne pass: node points to NULL, prev is that nodehead unchanged in effect
Two nodesTwo passes; the arrows swapOrder 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

MistakeConsequence
Flipping cur->next before saving itRest of the list is lost
Starting prev as headFirst node points to itself, creating an endless loop
Forgetting to update head at the endHead still points to the old first node, which is now the last
Reversing values instead of linksSlow, and fails for big payloads
Not testing the one-node listHidden 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), not p1, p2, p3; the names then explain the algorithm.
  • Take struct node **head so 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, cur and next.
  • Save, flip, advance prev, advance cur, in that order.
  • When the loop ends, prev is 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.

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 →