Loading…

mediumLinked ListsFrequently asked

Reverse a Doubly Linked List

Q: How do you solve Reverse a Doubly Linked List using the Iterative — Swap next/prev on Each Node (Optimal) approach?

When to use it: Lead with this. The per-node swap is the idiom interviewers want for DLL reversal, and it's O(1) space. We walk the list once and, at every node, exchange its `next` and `prev` so the node now points the opposite way. **Why a single swap per node suffices.** In a DLL, 'reversed' means: the node that was your successor should become your predecessor and vice versa. That is literally swapping the two pointer fields. There's no need to rebuild links across nodes — each node fixes its own two pointers, and because every node does it, the whole chain flips consistently. **Save the old next first — the lost-next trap.** The catch is that we navigate forward using `cur.next`, but the swap *overwrites* `cur.next` with the old `prev`. So before swapping we copy `cur.next` into a temp `nxt`. After swapping, `cur.next` points backward (useless for moving forward), so we advance with `cur = nxt`. Skip the save and you either loop forever (following the now-backward pointer) or stop one node in. **Why the new head is the old tail.** We keep updating `newHead = cur` on every iteration. The loop runs until `cur` becomes null, which happens right after we process the old tail. So the last node we touched — the old tail — is the node we return. Its old `next` was null, and after the swap that null lands in its `prev`, exactly the correct prev-of-head. **Why empty and single-node need no special case.** If `head` is null the loop body never runs and `newHead` stays null. For one node, `nxt` is null, we swap its two null-ish pointers, set `newHead = cur`, then `cur = null` ends the loop — the node is returned unchanged. Time complexity: O(n). Space complexity: O(1).

Q: How do you solve Reverse a Doubly Linked List using the Recursive — Swap at the Node, Recurse on the Old Next approach?

When to use it: Offer as a tidy alternative; flag the O(n) recursion stack versus the iterative O(1) space. We do the same per-node swap, but let the call stack drive the walk. **Base case identifies the new head.** If `head` is null, return null. Otherwise, after we swap the current node's pointers, if the saved old-next is null this node is the old tail — the new head — and we return it up the chain. **Swap, then recurse on the saved old-next.** Read `nxt = head.next` first (the lost-next trap applies here too), swap `head.next` and `head.prev`, then recurse on `nxt`. The recursive call reverses the remainder and returns the eventual new head, which every level simply passes upward unchanged — the actual relinking already happened via the local swap. **Why iterative is the safer lead.** The recursion mirrors the loop exactly but adds a stack frame per node. With n up to 10⁴ that risks a deep stack; the iterative O(1)-space version has no such limit. Same time, more space — present iterative first. Time complexity: O(n). Space complexity: O(n).

Linked List · 21 of 24 · 8 min

You are given the head of a doubly linked list, where each node has a val, a next pointer, and a prev pointer.

Reverse the list in place by re-pointing each node's links, and return the head of the reversed list.

Do not allocate new nodes — rewire the existing ones.

In plain English

In a doubly linked list every node points both forward (next) and backward (prev). Reversing means every node that used to point forward should now point backward and vice versa — so for each node we simply swap its next and prev. The old tail becomes the new head.

Examples

Example 1

Input: list = 1 <-> 2 <-> 3
Output: 3 <-> 2 <-> 1
Note: Each node swaps next/prev; node 3 (old tail) becomes the new head, node 1 (old head) becomes the new tail.

Example 2

Input: list = 1
Output: 1
Note: Single node: swapping its null next and null prev leaves it unchanged; it's its own head.

Example 3

Input: list = (empty)
Output: (empty)
Note: head is null, the loop never runs, and we return null.

Constraints

0 ≤ number of nodes ≤ 10⁴
-10⁵ ≤ Node.val ≤ 10⁵
Each node has both next and prev pointers (prev of head is null, next of tail is null)
Must run in O(1) extra space

Clarifying questions4First question: Is this a singly or doubly linked list?Explore questions

Q1.Is this a singly or doubly linked list?
Doubly — every node has both next and prev. That's what lets us reverse by swapping the two pointers per node instead of the three-pointer dance a singly linked list needs.
Q2.Can I mutate the existing nodes or must I build a new list?
Mutate in place. Swapping pointers gives O(1) extra space; rebuilding would waste O(n) memory.
Q3.What should I return for an empty or single-node list?
The same head. An empty list reverses to empty; a single node reverses to itself. Both fall out of the loop naturally.
Q4.After reversal, what should prev of the new head and next of the new tail be?
The new head's prev is null and the new tail's next is null — the swaps produce exactly that, since the old head's next was null becomes the old head's prev.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

For each node, swap its next and prev pointers, then move forward along the *old* next — which you must read before the swap, because the swap overwrites it. The last node you process becomes the new head. One pass, O(n) time, O(1) space, no new nodes.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize a DLL reversal is a per-node pointer swap rather than a rebuild, and whether you correctly save the forward pointer before overwriting it and return the old tail as the new head.

Where candidates slip

Advancing via cur.next after swapping (which now points backward, causing an infinite loop or early exit), or returning the original head instead of the last processed node.

How to stand out

State the two invariants: swap both pointers per node, and capture old-next first. Note the new head is the old tail, and that empty/single-node lists fall out of the loop for free — no special cases.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Iterative — Swap next/prev on Each Node (Optimal)Optimal	`O(n)`	`O(1)`	Lead with this. The per-node swap is the idiom interviewers want for DLL reversal, and it's O(1) space.	Read
2	Recursive — Swap at the Node, Recurse on the Old Next	`O(n)`	`O(n)`	Offer as a tidy alternative; flag the O(n) recursion stack versus the iterative O(1) space.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewReverse a doubly linked listNeed O(1) space?YesNo / prefer recursionExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Iterative — Swap next/prev on Each Node (Optimal)

TimeO(n)SpaceO(1)

Lead with this. The per-node swap is the idiom interviewers want for DLL reversal, and it's O(1) space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

In a doubly linked list each node already knows the node before and after it. If you flipped the meaning of those two fields on every node, which direction would the list read in?

2Hint 2Explore hint

Swapping cur.next and cur.prev destroys the forward link you need to keep walking. What must you grab before the swap?

3Hint 3Explore hint

After the loop ends, cur is null — so which node did you last touch, and what role does it now play in the reversed list?

A · Core idea

We walk the list once and, at every node, exchange its next and prev so the node now points the opposite way.

Why a single swap per node suffices. In a DLL, 'reversed' means: the node that was your successor should become your predecessor and vice versa. That is literally swapping the two pointer fields. There's no need to rebuild links across nodes — each node fixes its own two pointers, and because every node does it, the whole chain flips consistently.

Save the old next first — the lost-next trap. The catch is that we navigate forward using cur.next, but the swap overwrites cur.next with the old prev. So before swapping we copy cur.next into a temp nxt. After swapping, cur.next points backward (useless for moving forward), so we advance with cur = nxt. Skip the save and you either loop forever (following the now-backward pointer) or stop one node in.

Why the new head is the old tail. We keep updating newHead = cur on every iteration. The loop runs until cur becomes null, which happens right after we process the old tail. So the last node we touched — the old tail — is the node we return. Its old next was null, and after the swap that null lands in its prev, exactly the correct prev-of-head.

Why empty and single-node need no special case. If head is null the loop body never runs and newHead stays null. For one node, nxt is null, we swap its two null-ish pointers, set newHead = cur, then cur = null ends the loop — the node is returned unchanged.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

list = 1 <-> 2 <-> 3

Array state

cur on 1

save nxt=2, swap 1's next/prev

cur ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result3 <-> 2 <-> 1

C · Code with teaching comments

solution.javaJava

Iterative — Swap next/prev on Each Node (Optimal) — optimal

5 teaching notes

1
public class DoublyLinkedListNode {
2
    int val;
3
    DoublyLinkedListNode next;
4
    DoublyLinkedListNode prev;
5
    DoublyLinkedListNode() {}
6
    DoublyLinkedListNode(int val) { this.val = val; }
7
}
8
 
9
public DoublyLinkedListNode reverse(DoublyLinkedListNode head) {
10
    DoublyLinkedListNode cur = head;
11
    DoublyLinkedListNode newHead = head;
12
    while (cur != null) {
13
        // Capture the forward pointer BEFORE the swap clobbers it — the lost-next trap.
14
        DoublyLinkedListNode nxt = cur.next;
15
        // First half of the swap: the old predecessor becomes the new successor.
16
        cur.next = cur.prev;
17
        // Second half: the saved old successor becomes the new predecessor.
18
        cur.prev = nxt;
19
        // Track the last node touched — the old tail will be the final value, our new
20
        // head.
21
        newHead = cur;
22
        // Advance using the saved old-next, NOT cur.next (which now points backward).
23
        cur = nxt;
24
    }
25
    return newHead;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The whole trick is recognizing that DLL reversal decomposes into n independent per-node swaps. The only cross-node concern is preserving the forward pointer before the swap eats it — the same 'stash the next pointer' reflex from every in-place list rewrite.

ComplexityO(n) time, O(1) space — Exactly one visit per node, each doing O(1) pointer swaps → O(n) time. Only a couple of temp pointers are used → O(1) space.

E · Edge cases and pitfalls7list = (empty) — head is null; loop never runs; newHead stays null → returns null.Explore edge cases

Edge cases handled

list = (empty)head is null; loop never runs; newHead stays null → returns null.
list = 1nxt = null, swap leaves the single node's pointers null, newHead = node, cur = null → returns the same node.
list = 1 <-> 2Process 1 (nxt=2, swap), then 2 (nxt=null, swap), newHead = 2 → 2 <-> 1.

Pitfalls

Advancing with cur = cur.next after the swap — that pointer now goes backward, causing an infinite loop or premature stop.
Swapping only next (or only prev) — leaves the list inconsistent and corrupt.
Returning the original head instead of the last node (old tail).
Forgetting to save old-next before swapping — the lost-next trap that strands the rest of the list.

03.2

Approach 2 of 2

Recursive — Swap at the Node, Recurse on the Old Next

TimeO(n)SpaceO(n)

Offer as a tidy alternative; flag the O(n) recursion stack versus the iterative O(1) space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you swap the current node's next/prev, what's left to reverse, and where does the new head come from?

2Hint 2Explore hint

Save the old next before swapping, then recurse on that saved node.

3Hint 3Explore hint

The base case is reaching null or the old tail — the node with no old-next is the new head that bubbles back up.

A · Core idea

We do the same per-node swap, but let the call stack drive the walk.

Base case identifies the new head. If head is null, return null. Otherwise, after we swap the current node's pointers, if the saved old-next is null this node is the old tail — the new head — and we return it up the chain.

Swap, then recurse on the saved old-next. Read nxt = head.next first (the lost-next trap applies here too), swap head.next and head.prev, then recurse on nxt. The recursive call reverses the remainder and returns the eventual new head, which every level simply passes upward unchanged — the actual relinking already happened via the local swap.

Why iterative is the safer lead. The recursion mirrors the loop exactly but adds a stack frame per node. With n up to 10⁴ that risks a deep stack; the iterative O(1)-space version has no such limit. Same time, more space — present iterative first.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

list = 1 <-> 2 <-> 3

Interactive diagram

Recursion swaps then forwards the new head

rev(1)

Active call / nodeSupporting contextReturned stateNot active

Each frame swaps its node and recurses; the old tail becomes the new head and bubbles back through every return.

Final result3 <-> 2 <-> 1

C · Code with teaching comments

Reference implementation previewpublic DoublyLinkedListNode reverse(DoublyLinkedListNode head) { if (head == null) return null; DoublyLinkedListNode nxt = head.next; head.next = head.prev; head.prev = nxt;Explore the full code

solution.javaJava

Recursive — Swap at the Node, Recurse on the Old Next — reference

5 teaching notes

1
public DoublyLinkedListNode reverse(DoublyLinkedListNode head) {
2
    // Empty list base case — nothing to reverse.
3
    if (head == null) return null;
4
    // Save old-next before the swap destroys it.
5
    DoublyLinkedListNode nxt = head.next;
6
    // Swap this node's two pointers, flipping its direction.
7
    head.next = head.prev;
8
    head.prev = nxt;
9
    // No old-next means this is the old tail = new head; return it.
10
    if (nxt == null) return head;
11
    // Recurse on the saved old-next and pass the eventual new head straight up.
12
    return reverse(nxt);
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Recursion turns the explicit newHead bookkeeping into a return value: the base case (old tail) hands the new head back up, and each frame just forwards it. The per-node swap is identical to the loop — only the driver changes.

ComplexityO(n) time, O(n) space — One call per node → O(n) calls, each O(1) work → O(n) time. Recursion depth equals the node count → O(n) stack space.

E · Edge cases and pitfalls3Swapping after reading head.next incorrectly — always save old-next first.Explore edge cases

Pitfalls

Swapping after reading head.next incorrectly — always save old-next first.
Recursing on head.next after the swap — it now points backward; recurse on the saved nxt.
Deep recursion on long lists risks stack overflow where the iterative version is safe.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic class DoublyLinkedListNode { int val; DoublyLinkedListNode next; DoublyLinkedListNode prev; DoublyLinkedListNode() {}Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Walking forward with the post-swap next pointer

After the swap, cur.next holds the old prev — it points backward. Using it to advance either revisits earlier nodes forever or exits after one step. You must move along the saved old-next.

Explore the code comparison

Don't write this

DoublyLinkedListNode nxt = cur.next;
cur.next = cur.prev;
cur.prev = nxt;
cur = cur.next;   // now points backward!

Write this instead

DoublyLinkedListNode nxt = cur.next;
cur.next = cur.prev;
cur.prev = nxt;
cur = nxt;        // saved old-next

Swapping only one pointer

Reversal requires both fields to flip. Setting next but not prev (or vice versa) leaves nodes whose forward and backward links disagree, corrupting any later traversal in either direction.

Explore the code comparison

Don't write this

nxt = cur.next
cur.next = cur.prev
# forgot: cur.prev = nxt
cur = nxt

Write this instead

nxt = cur.next
cur.next = cur.prev
cur.prev = nxt
cur = nxt

Returning the original head

After reversal the original head is the new tail. Returning it hands back a node whose next is null, so the caller sees a one-node list. The new head is the last node processed (old tail).

Explore the code comparison

Don't write this

while cur is not None:
    # ... swap ...
    cur = nxt
return head   # head is now the tail!

Write this instead

new_head = head
while cur is not None:
    # ... swap ...
    new_head = cur
    cur = nxt
return new_head

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Swap next/prev per node, walk along the saved old-next, return the last node as head

Code pattern to memorize

cur = head
newHead = head
while cur:
    nxt = cur.next        # read before swapping
    cur.next = cur.prev
    cur.prev = nxt
    newHead = cur
    cur = nxt
return newHead

Rules to remember

1Save cur.next into a temp before swapping — the swap destroys it and you lose your way forward (the lost-next trap).
2Swap both pointers per node: next ↔ prev. Touching only one leaves the list half-rewired and corrupt.
3The new head is the last node you process (the old tail), not head — return it.
4Advance using the saved old-next, never cur.next after the swap (which now points backward).
5An empty or single-node list reverses to itself — the loop handles both without special branches.

Use this pattern when

Reverse a list that has both next and prev links (doubly linked)
You need O(1) extra space and can mutate the existing nodes
Any 'flip the direction of traversal' task on a bidirectional structure
Preparing a DLL for backward iteration or LRU-style reordering

Choose another pattern when

The list is singly linked → there is no prev to swap; use the three-pointer prev/cur/next reversal
You must keep the original order intact → copy or iterate backward instead of mutating
Only a backward *view* is needed, not a true reversal → just walk prev pointers from the tail
Nodes are immutable → you cannot swap fields; rebuild instead

Interview takeaway

Reversing a DLL is just 'swap next and prev on every node'. The only subtlety is reading the old next before the swap clobbers it, and remembering the new head is the old tail. Master this and reverse-a-sublist and rotate on a DLL follow directly.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternIn-place pointer manipulation on a doubly linked list: every node swaps its next and prev, the old tail becomes the new head. The same per-node rewiring underlies DLL splicing in LRU Cache and reverse-a-sublist on bidirectional lists.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Merge Two Sorted Linked Lists

Continue · Next problem

Insert a Node at the Tail of a Linked List

mediumLinked ListsFrequently asked

Reverse a Doubly Linked List

Linked List · 21 of 24 · 8 min

You are given the head of a doubly linked list, where each node has a val, a next pointer, and a prev pointer.

Reverse the list in place by re-pointing each node's links, and return the head of the reversed list.

Do not allocate new nodes — rewire the existing ones.

In plain English

Examples

Example 1

Input: list = 1 <-> 2 <-> 3
Output: 3 <-> 2 <-> 1
Note: Each node swaps next/prev; node 3 (old tail) becomes the new head, node 1 (old head) becomes the new tail.

Example 2

Input: list = 1
Output: 1
Note: Single node: swapping its null next and null prev leaves it unchanged; it's its own head.

Example 3

Input: list = (empty)
Output: (empty)
Note: head is null, the loop never runs, and we return null.

Constraints

0 ≤ number of nodes ≤ 10⁴
-10⁵ ≤ Node.val ≤ 10⁵
Each node has both next and prev pointers (prev of head is null, next of tail is null)
Must run in O(1) extra space

Clarifying questions4First question: Is this a singly or doubly linked list?Explore questions

Q1.Is this a singly or doubly linked list?
Doubly — every node has both next and prev. That's what lets us reverse by swapping the two pointers per node instead of the three-pointer dance a singly linked list needs.
Q2.Can I mutate the existing nodes or must I build a new list?
Mutate in place. Swapping pointers gives O(1) extra space; rebuilding would waste O(n) memory.
Q3.What should I return for an empty or single-node list?
The same head. An empty list reverses to empty; a single node reverses to itself. Both fall out of the loop naturally.
Q4.After reversal, what should prev of the new head and next of the new tail be?
The new head's prev is null and the new tail's next is null — the swaps produce exactly that, since the old head's next was null becomes the old head's prev.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize a DLL reversal is a per-node pointer swap rather than a rebuild, and whether you correctly save the forward pointer before overwriting it and return the old tail as the new head.

Where candidates slip

Advancing via cur.next after swapping (which now points backward, causing an infinite loop or early exit), or returning the original head instead of the last processed node.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Iterative — Swap next/prev on Each Node (Optimal)Optimal	`O(n)`	`O(1)`	Lead with this. The per-node swap is the idiom interviewers want for DLL reversal, and it's O(1) space.	Read
2	Recursive — Swap at the Node, Recurse on the Old Next	`O(n)`	`O(n)`	Offer as a tidy alternative; flag the O(n) recursion stack versus the iterative O(1) space.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Iterative — Swap next/prev on Each Node (Optimal)

TimeO(n)SpaceO(1)

Lead with this. The per-node swap is the idiom interviewers want for DLL reversal, and it's O(1) space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

In a doubly linked list each node already knows the node before and after it. If you flipped the meaning of those two fields on every node, which direction would the list read in?

2Hint 2Explore hint

Swapping cur.next and cur.prev destroys the forward link you need to keep walking. What must you grab before the swap?

3Hint 3Explore hint

After the loop ends, cur is null — so which node did you last touch, and what role does it now play in the reversed list?

A · Core idea

We walk the list once and, at every node, exchange its next and prev so the node now points the opposite way.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

list = 1 <-> 2 <-> 3

Array state

cur on 1

save nxt=2, swap 1's next/prev

cur ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result3 <-> 2 <-> 1

C · Code with teaching comments

solution.javaJava

Iterative — Swap next/prev on Each Node (Optimal) — optimal

5 teaching notes

1
public class DoublyLinkedListNode {
2
    int val;
3
    DoublyLinkedListNode next;
4
    DoublyLinkedListNode prev;
5
    DoublyLinkedListNode() {}
6
    DoublyLinkedListNode(int val) { this.val = val; }
7
}
8
 
9
public DoublyLinkedListNode reverse(DoublyLinkedListNode head) {
10
    DoublyLinkedListNode cur = head;
11
    DoublyLinkedListNode newHead = head;
12
    while (cur != null) {
13
        // Capture the forward pointer BEFORE the swap clobbers it — the lost-next trap.
14
        DoublyLinkedListNode nxt = cur.next;
15
        // First half of the swap: the old predecessor becomes the new successor.
16
        cur.next = cur.prev;
17
        // Second half: the saved old successor becomes the new predecessor.
18
        cur.prev = nxt;
19
        // Track the last node touched — the old tail will be the final value, our new
20
        // head.
21
        newHead = cur;
22
        // Advance using the saved old-next, NOT cur.next (which now points backward).
23
        cur = nxt;
24
    }
25
    return newHead;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — Exactly one visit per node, each doing O(1) pointer swaps → O(n) time. Only a couple of temp pointers are used → O(1) space.

E · Edge cases and pitfalls7list = (empty) — head is null; loop never runs; newHead stays null → returns null.Explore edge cases

Edge cases handled

list = (empty)head is null; loop never runs; newHead stays null → returns null.
list = 1nxt = null, swap leaves the single node's pointers null, newHead = node, cur = null → returns the same node.
list = 1 <-> 2Process 1 (nxt=2, swap), then 2 (nxt=null, swap), newHead = 2 → 2 <-> 1.

Pitfalls

Advancing with cur = cur.next after the swap — that pointer now goes backward, causing an infinite loop or premature stop.
Swapping only next (or only prev) — leaves the list inconsistent and corrupt.
Returning the original head instead of the last node (old tail).
Forgetting to save old-next before swapping — the lost-next trap that strands the rest of the list.

03.2

Approach 2 of 2

Recursive — Swap at the Node, Recurse on the Old Next

TimeO(n)SpaceO(n)

Offer as a tidy alternative; flag the O(n) recursion stack versus the iterative O(1) space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you swap the current node's next/prev, what's left to reverse, and where does the new head come from?

2Hint 2Explore hint

Save the old next before swapping, then recurse on that saved node.

3Hint 3Explore hint

The base case is reaching null or the old tail — the node with no old-next is the new head that bubbles back up.

A · Core idea

We do the same per-node swap, but let the call stack drive the walk.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

list = 1 <-> 2 <-> 3

Interactive diagram

Recursion swaps then forwards the new head

rev(1)

Active call / nodeSupporting contextReturned stateNot active

Each frame swaps its node and recurses; the old tail becomes the new head and bubbles back through every return.

Final result3 <-> 2 <-> 1

C · Code with teaching comments

solution.javaJava

Recursive — Swap at the Node, Recurse on the Old Next — reference

5 teaching notes

1
public DoublyLinkedListNode reverse(DoublyLinkedListNode head) {
2
    // Empty list base case — nothing to reverse.
3
    if (head == null) return null;
4
    // Save old-next before the swap destroys it.
5
    DoublyLinkedListNode nxt = head.next;
6
    // Swap this node's two pointers, flipping its direction.
7
    head.next = head.prev;
8
    head.prev = nxt;
9
    // No old-next means this is the old tail = new head; return it.
10
    if (nxt == null) return head;
11
    // Recurse on the saved old-next and pass the eventual new head straight up.
12
    return reverse(nxt);
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — One call per node → O(n) calls, each O(1) work → O(n) time. Recursion depth equals the node count → O(n) stack space.

E · Edge cases and pitfalls3Swapping after reading head.next incorrectly — always save old-next first.Explore edge cases

Pitfalls

Swapping after reading head.next incorrectly — always save old-next first.
Recursing on head.next after the swap — it now points backward; recurse on the saved nxt.
Deep recursion on long lists risks stack overflow where the iterative version is safe.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic class DoublyLinkedListNode { int val; DoublyLinkedListNode next; DoublyLinkedListNode prev; DoublyLinkedListNode() {}Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Walking forward with the post-swap next pointer

After the swap, cur.next holds the old prev — it points backward. Using it to advance either revisits earlier nodes forever or exits after one step. You must move along the saved old-next.

Explore the code comparison

Don't write this

DoublyLinkedListNode nxt = cur.next;
cur.next = cur.prev;
cur.prev = nxt;
cur = cur.next;   // now points backward!

Write this instead

DoublyLinkedListNode nxt = cur.next;
cur.next = cur.prev;
cur.prev = nxt;
cur = nxt;        // saved old-next

Swapping only one pointer

Reversal requires both fields to flip. Setting next but not prev (or vice versa) leaves nodes whose forward and backward links disagree, corrupting any later traversal in either direction.

Explore the code comparison

Don't write this

nxt = cur.next
cur.next = cur.prev
# forgot: cur.prev = nxt
cur = nxt

Write this instead

nxt = cur.next
cur.next = cur.prev
cur.prev = nxt
cur = nxt

Returning the original head

After reversal the original head is the new tail. Returning it hands back a node whose next is null, so the caller sees a one-node list. The new head is the last node processed (old tail).

Explore the code comparison

Don't write this

while cur is not None:
    # ... swap ...
    cur = nxt
return head   # head is now the tail!

Write this instead

new_head = head
while cur is not None:
    # ... swap ...
    new_head = cur
    cur = nxt
return new_head

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Swap next/prev per node, walk along the saved old-next, return the last node as head

Code pattern to memorize

cur = head
newHead = head
while cur:
    nxt = cur.next        # read before swapping
    cur.next = cur.prev
    cur.prev = nxt
    newHead = cur
    cur = nxt
return newHead

Rules to remember

1Save cur.next into a temp before swapping — the swap destroys it and you lose your way forward (the lost-next trap).
2Swap both pointers per node: next ↔ prev. Touching only one leaves the list half-rewired and corrupt.
3The new head is the last node you process (the old tail), not head — return it.
4Advance using the saved old-next, never cur.next after the swap (which now points backward).
5An empty or single-node list reverses to itself — the loop handles both without special branches.

Use this pattern when

Reverse a list that has both next and prev links (doubly linked)
You need O(1) extra space and can mutate the existing nodes
Any 'flip the direction of traversal' task on a bidirectional structure
Preparing a DLL for backward iteration or LRU-style reordering

Choose another pattern when

The list is singly linked → there is no prev to swap; use the three-pointer prev/cur/next reversal
You must keep the original order intact → copy or iterate backward instead of mutating
Only a backward *view* is needed, not a true reversal → just walk prev pointers from the tail
Nodes are immutable → you cannot swap fields; rebuild instead

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Merge Two Sorted Linked Lists

Continue · Next problem

Insert a Node at the Tail of a Linked List