cf.completefrontend
LINKED LISTS · CORE

Linked list reversal

Turn every next link around, one node at a time, so the list runs backwards using no extra memory.

Time O(n)Space O(1)8 practice problemsStep-through picture

The idea

Reversing a linked list means the last node becomes the first and every next link points the other way. You don't create new nodes or move values. You walk the list once and flip each node's next link so it points to the node before it.

The trick is that flipping curr.next loses the way forward. So the loop keeps three pointers: prev (the part already reversed), curr (the node being flipped), and next (saved before the flip so the rest of the list isn't lost).

This small loop is a building block. Many problems reverse only part of a list, reverse groups of k nodes, or reverse the second half to compare it with the first.

An everyday example

Turning a conga line around

In a conga line, each dancer holds the shoulders of the person in front. To make the line go the other way, you walk along it, and each dancer lets go and turns to hold the dancer who was behind them. Before a dancer lets go, you note who they were holding, or you'd lose track of the rest of the line.

How the example maps to the code
In the exampleIn the code
The dancers already turned aroundprev, the reversed part
The dancer turning nowcurr
Noting who they held before letting goconst next = curr.next
Turning to hold the dancer behindcurr.next = prev
The old last dancer now leadsreturn prev

From the slow way to linked list reversal

  1. Start with the obvious way: walk the list and copy every value into an array, then walk the list again and write the values back from the end of the array. It takes O(n) time, but it also needs an O(n) array, and it changes the values in the nodes instead of the order of the nodes, which breaks any code that holds a reference to a node and expects its value to stay put.
  2. A reversed list contains the same nodes. Only the direction of each link changes: if 14.next was 21, it should become 7, the node that came before it. And while walking forward, the node that came before is exactly the one you just left. So each link can be flipped during a single walk, as long as you remember the previous node in prev.
  3. Flipping has one trap. The moment you write curr.next = prev, the only link to the rest of the list is gone. So the loop saves it first in next, flips, and then steps into the saved rest. Three pointers: the reversed part (prev), the node being flipped (curr), and the untouched part (next).
  4. Two details finish it. prev starts at null, so the old first node ends up pointing to null and becomes the end. And when curr runs out, prev is the old last node, the new head. That loop is in-place linked list reversal.

How it works

  1. Set prev to null (the reversed part is empty) and curr to head.
  2. While curr is not null, save the rest of the list: next = curr.next.
  3. Flip the link: curr.next = prev.
  4. Grow the reversed part: prev = curr.
  5. Step forward into the saved rest: curr = next.
  6. When curr is null, prev is the old last node, the new head. Return it.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function reverseList(head) {
  2. let prev = null;
  3. let curr = head;
  4. while (curr !== null) {
  5. const next = curr.next;
  6. curr.next = prev;
  7. prev = curr;
  8. curr = next;
  9. }
  10. return prev;
  11. }

How fast it is

TimeO(n)
Extra memoryO(1)

Each node is visited once and gets one link changed. Only three pointers are kept, whatever the length.

  • Best caseO(n)

    Any list. Every one of the n links must point the other way, so even the friendliest input needs one loop per node.

  • Average caseO(n)

    Any list: the work depends only on the length, never on the values.

  • Worst caseO(n)

    Any list: n loops, each with one saved pointer, one link write, and two moves.

Common mistakes

  • Setting curr.next = prev before saving curr.next. The rest of the list is lost and the loop stops after one node.
  • Returning head instead of prev. After reversing, head is the last node, so you return a one-node list.
  • Forgetting that the old head must end with next = null. Starting prev at null does this; starting it anywhere else creates a cycle.
  • When reversing a part of the list, forgetting to reconnect both ends, which cuts the list or creates a loop.

When to use it

Look for these clues in a problem:

  • The task asks to reverse a list, a part of it, or groups of nodes.
  • You need to read a list backwards but must use O(1) extra space.
  • You need to compare the first half of a list with the second half read backwards.
  • Numbers are stored digit by digit in a list and you need to process them from the other end.

Check yourself

Answer each one in your head first, then open it.

Why must next be saved before curr.next = prev?

After that line, curr.next points backward, and nothing else points to the rest of the list. Without the saved next, the walk can't continue.

Why does prev start as null instead of head?

The old head becomes the last node, and the last node's next must be null. Starting prev at head would make the head point to itself, a cycle.

How many link writes does reversing a list of n nodes take?

Exactly n, one curr.next = prev per node. The trace on four nodes wrote four links.

What does the function return, and why not head?

It returns prev, the old last node. head still points to the old first node, which is now the end of the list.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 8 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule at the top of every loop: prev is the head of a correctly reversed list made of every node before curr, ending in null, and curr is the head of the untouched rest. The two parts share no nodes. At the start, the reversed part is empty (prev = null) and the untouched part is the whole list, so the rule holds.

Each loop moves exactly one node from the front of the untouched part to the front of the reversed part. Saving next first keeps the untouched part reachable. Writing curr.next = prev puts curr in front of the reversed part. Then prev = curr and curr = next restore the rule with one more node reversed.

The untouched part shrinks by one node every loop, so on a list with an end the loop stops after n loops. At that point the untouched part is empty, so by the rule prev heads a reversed list of every node, ending in null. That is the answer.

Going deeper

3 more ideas

The rule each loop keeps

At the start of each loop, the nodes before curr form a reversed list that starts at prev, and the nodes from curr onward are untouched. Each loop moves one node from the untouched part to the front of the reversed part. When the untouched part is empty, the whole list is reversed and starts at prev.

Reversing only a part

To reverse the nodes from position left to right, walk a pointer before to the node just in front of left (start at a dummy node so this works when left is 1). Reverse right - left + 1 nodes with the same loop. Then reconnect: the old first node of the part (now its last) links to curr, and before.next points to prev, the part's new first node.

Cost, and the recursive version

The loop touches each node once, so it is O(n) time and O(1) extra space. A recursive version (reverse the rest, then hook the current node on the end) is shorter to write but uses one stack frame per node, O(n) space, and can overflow the call stack on a list of 100,000 nodes.

Work it by hand

Every step in a table, with why

Reverse a four-node list in place. Each row is one pass through the loop.

head = 7 -> 14 -> 21 -> 28

Stepcurrnext (saved)FlipReversed part from prevUntouched partWhy
17147.next = null714 -> 21 -> 28prev starts as null, so the old head now ends the list. Then prev = 7 and curr = 14.
2142114.next = 714 -> 721 -> 2814 now points back to 7. The saved next, 21, keeps the way forward.
3212821.next = 1421 -> 14 -> 728The reversed part grows at its front by one node each loop.
428null28.next = 2128 -> 21 -> 14 -> 7emptyThe last node is flipped. The saved next is null, so curr becomes null.
5null--28 -> 21 -> 14 -> 7emptycurr is null, so the loop stops. Every node has been moved to the reversed part.

It returns prev, the node 28, giving 28 -> 21 -> 14 -> 7 after 4 loops and 4 link writes. The variable head still points to 7, which is now the last node, so returning head would give a one-node list.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Linked list reversalO(n)O(1)You need the nodes in the other order and can change their links.
Recursive reversalO(n)O(n)The list is short and you prefer the shorter code. Avoid it for long lists because of the call stack.
Copy into an array or stack, then rebuildO(n)O(n)You must not change the original list, or you only need to read the values backwards once.

Extra memory: O(1): three pointers, prev, curr, and next. The recursive version uses O(n) space for its call stack instead.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Linked list reversal and the other approaches, on a scale where each line up is 10 times more steps.
  • Linked list reversal, Recursive reversal, Copy into an array or stack, then rebuild O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Linked list reversal101,0001 million
Recursive reversal101,0001 million
Copy into an array or stack, then rebuild101,0001 million

Inputs that need care

5 tricky inputs
An empty list: head = null
The loop never runs and the function returns prev, which is null.
One node
One loop sets its next to null (it already was) and returns it. The list is its own reverse.
Two nodes, 5 -> 9
Two loops: 5.next = null, then 9.next = 5. It returns 9 -> 5. This is the smallest list where a missing save of next shows up.
Other code still holds the old head
That reference now points to the last node, whose next is null. Anything that walks from it sees a one-node list, so update every saved head after reversing.
A list that loops back, like 1 -> 2 -> 3 -> 4 -> 5 with 5.next = 3
The loop does end, because flipped links lead it back along the path to the old head, whose next is null. On this list it runs 8 times and returns the node 1, but the result is a scrambled loop, not a reversed list. Check for a cycle first if the data can be broken.

Variations and follow-ups

Twists interviewers add

Reverse a part of the list

To reverse positions left to right, walk a pointer before from a dummy node to the node just in front of left. Run the same loop right - left + 1 times. Then join the ends: the part's old first node, now its last, links to curr, and before.next becomes prev.

Reverse in groups of k

First check that at least k nodes remain, then reverse exactly k nodes and attach the group behind the previous group's last node. Leave a short final group as it is, or reverse it too, as the task says. Each node is still flipped once, so the total is O(n).

Recursive reversal

Reverse everything after head, then make head.next.next = head and head.next = null, and return the new head from the deeper call. It is short, but each node adds a stack frame, so a list of 100,000 nodes can throw "Maximum call stack size exceeded".

Reverse the second half to compare

Find the middle with fast and slow pointers, reverse the second half, and walk both halves together. This checks whether a list reads the same both ways, or folds a list as first, last, second, second-last, in O(1) space.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "reverse", "read from the end", "compare the first half with the second half", or "reorder the list" with an O(1) space limit.
  • Name the three pointers before coding and say what each one means: "prev heads the reversed part, curr is the node I'm flipping, next is the saved rest". Then write the four lines in the order save, flip, advance prev, advance curr.
  • Test by hand on lists of length 0, 1, and 2. If you forget to save next, the two-node list stops after one loop.
  • Expect the follow-up "now reverse only positions left to right". Answer with a dummy node, the same loop for right - left + 1 nodes, and the two reconnecting links.

Where frontend code uses it

The same idea in real UI code
  • Undo history is often kept as a chain of states linked from newest to oldest. Showing it oldest first, for example in a history panel, means walking it reversed.
  • Linked chains such as a component's parent links run from the leaf up to the root. Reversing that path gives the root-to-leaf order you need for breadcrumbs or for event capture order.
  • Reversing a list in place is the core step of folding and comparing list halves, and of reversing groups of items without copying them.

Related algorithms