AlgoViz
HomeLinked List

Reverse a Doubly Linked List

Medium

Swap prev and next at every node

Problem

You are given the head of a doubly linked list. Reverse the list in-place and return the new head of the reversed list.

In simple words

Swap the previous and next pointers of every node, then the old tail becomes the head.

The idea

Because each node already stores both directions, reversing is just exchanging its two pointers and then returning the node you finished on. No rewiring of neighbours is needed — the swap does it implicitly.

The trick

  • Save next before swapping or you lose your place in the walk.
  • The new head is the last node you visited.
  • O(n) time, O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

10
20
30
0
1
2

Step 1 of 2. Here's the example — head = [10, 20, 30] Values: 10, 20, 30.

1/2
Optimal
timeO(n)spaceO(1)
1cur = head; last = null2while cur != null:3  swap(cur.prev, cur.next)4  last = cur5  cur = cur.prev        // moved because swapped6return last

Input

array
[10, 20, 30]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 3 -> 4
Output:
4 -> 3 -> 2 -> 1
Explanation:
Swap each node's prev/next pointers.

Example 2

Input:
list = 10 -> 20
Output:
20 -> 10
Explanation:
Two nodes flip.

Example 3

Input:
list = 5
Output:
5
Explanation:
One node stays.

Constraints

  • 1 <= number of nodes <= 10^6
  • 0 <= node.val <= 10^4

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.