☕ DSA Java Articles

Topics › Linked List › Learn Doubly LinkedList

Reverse a Doubly Linked List

Medium TUF ID 900 A2Z

Java source ↗ Edit this article ↗

Problem

You are given the head of a doubly linked list. Reverse the order of its nodes and return the head of the reversed list. Afterwards, walking forward from the returned head must visit the original values from last to first, every prev link must mirror the corresponding next link, and the new head’s prev must be null.

Constraints: 0 ≤ n ≤ 10^5 nodes, values fit in a 32-bit signed integer. The ideal solution uses O(1) extra space and rewires the existing nodes rather than allocating new ones.

Example 1

list = 1 <-> 2 <-> 3 <-> 4 <-> 5
answer = 5 <-> 4 <-> 3 <-> 2 <-> 1

Example 2

list = 1
answer = 1                          // a single node is its own reverse

Example 3

list = (empty)
answer = (empty)

The node type carries a value and two references.

static class Node {
    int val;
    Node prev, next;
    Node(int val) { this.val = val; }
    Node(int val, Node prev, Node next) { this.val = val; this.prev = prev; this.next = next; }
}

Approach 1: Brute force, reverse the values

Intuition. The simplest way to make the list read backwards is to leave the nodes where they are and move the values. A stack reverses order for free: push every value during a forward pass, then pop during a second forward pass and write the popped value into each node. The first node receives the last value pushed, which is the old tail’s value, and so on. No link changes at all, so the list is trivially still well formed.

Algorithm.

  1. Traverse the list and push each val onto a stack.
  2. Traverse again from the head; at each node, pop the stack and store the value in val.
  3. Return the same head.
static Node bruteForce(Node head) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (Node t = head; t != null; t = t.next) stack.push(t.val);
    for (Node t = head; t != null; t = t.next) t.val = stack.pop();    // pops come out in reverse order
    return head;
}

Complexity. Time O(n): two passes. Space O(n) for the stack of values.

This is a legitimate answer when only the sequence of values matters, but it does not actually reverse the list: the head node object is still the head (the tests check bruteForce(same) == same). In problems where other code holds references to specific nodes, or where the node payload is large and should not be copied, moving values is the wrong tool. It also costs O(n) extra memory where the optimal approach needs none.

Approach 2: Optimal, swap prev and next in every node

Intuition. In a doubly linked list every node already knows both of its neighbours. Reversing the list means that what used to be “after” should now be “before” and vice versa, and that is exactly a swap of the two fields prev and next inside each node. No node needs to look at any other node to do its own swap. The only subtlety is navigation: once next is overwritten we can no longer use it to move forward, so the old next must be saved before the swap. The last node we visit is the old tail, and after its swap it has prev == null, so it is the new head.

Algorithm.

  1. Set current = head and newHead = head.
  2. While current != null:
    • save oldNext = current.next;
    • set current.next = current.prev and current.prev = oldNext;
    • record newHead = current (the most recently flipped node);
    • advance current = oldNext.
  3. Return newHead.
static Node optimal(Node head) {
    Node current = head;
    Node newHead = head;
    while (current != null) {
        Node oldNext = current.next;      // remember where to go before the links are flipped
        current.next = current.prev;      // flip
        current.prev = oldNext;           // flip
        newHead = current;                // whichever node we flip last is the old tail = new head
        current = oldNext;
    }
    return newHead;
}

Complexity. Time O(n): each node is visited once and does constant work. Space O(1): three references.

Dry run on 1 <-> 2 <-> 3. Each row shows the state after the node in the first column has been flipped.

flipped its prev its next newHead current moves to
1 [2] null [1] [2]
2 [3] [1] [2] [3]
3 null [2] [3] null

Reading forward from newHead = 3: 3 -> 2 -> 1 -> null. Reading prev from 1: 1.prev = 2, 2.prev = 3, 3.prev = null. Every forward link is mirrored, so the list is well formed, and the old head 1 is now the tail with next == null. The tests confirm these facts on real node objects (newHead == oldTail, head.next == null) and run a full backward traversal plus a well-formedness check on every result.

Why the empty and single-node lists need no special case: for null, the loop never runs and newHead = head = null. For one node, both links are null, swapping them changes nothing, and the node is returned as the head.

Reversing twice must restore the original list, which is a cheap and strong self-test; the Java file does it on every input.

Approach 2, the classic form

Intuition. The version most often shown in TUF and textbooks performs the same swap but navigates through current.prev after the swap instead of a saved variable, and keeps a single last reference. After the loop, last holds the old tail’s old prev, which after the swap is that node’s next; so last.prev is the old tail, the new head. It is terser, but the reasoning about which pointer means what after the swap is harder to follow, which is why the version above is presented first.

Algorithm.

  1. If the list has fewer than two nodes, return it as is.
  2. For each node: save last = current.prev, swap current.prev and current.next via last, then move current = current.prev (the old next).
  3. Return last.prev.
static Node optimalClassic(Node head) {
    if (head == null || head.next == null) return head;
    Node last = null;
    Node current = head;
    while (current != null) {
        last = current.prev;
        current.prev = current.next;
        current.next = last;
        current = current.prev;           // prev now holds the old next
    }
    return last.prev;                     // last is the old tail's old prev; after the swap its prev is the old tail
}

Complexity. Time O(n), space O(1). It is tested against the same expected output as optimal and bruteForce on every input.

The early return exists because last.prev would be a null dereference for an empty list, and for a single node last would also be null. In the first approach, tracking newHead explicitly removes both special cases.

Edge cases and pitfalls