Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Reverse a Doubly Linked List in Java: Exchange Both Links

Reverse next and prev pointers in place, trace the saved original-next link, preserve node identity and choose safe iteration for long Java lists.

EasyRecursion and backtrackingPattern: recursion, reversal

Problem statement

Reverse a doubly linked list in place and return the new head. The values should read backward when following next, and every prev link must also be correct. Reuse the original nodes; swapping displayed values is not the requested structural reversal.

The supplied task allows up to 1,000,000 nodes with values 0–10,000. That makes recursion a useful explanation but an unsafe full-bound Java implementation. GFG practice supplies its own node type; adapt DllNode to that signature. Both methods below defensively handle a null head.

Constraints & requirements

CONTRACT
Original task allows up to 1,000,000 nodes. Recursive explanation uses O(n) stack and is unsuitable at that size; the iterative version uses O(1) extra space. A null head is handled defensively.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    10 ⇄ 20 ⇄ 30
    Output
    30 ⇄ 20 ⇄ 10

    Old tail becomes head; every next/prev relation is exchanged.

  2. Example 2 Case 2

    Input
    42
    Output
    42

    Both endpoint links remain null.

  3. Example 3 Case 3

    Input
    1 ⇄ 1 ⇄ 2
    Output
    2 ⇄ 1 ⇄ 1

    Reverse node identities, not just displayed values.

Solve on GeeksforGeeks ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

The old predecessor must become the new successor.

02Hint 2

Save original next before swapping both pointers.

03Hint 3

Continue along the saved link; use a loop for long Java lists.

How to think before coding

Before changing any link, save originalNext. The old prev must become next, and the old next must become prev. Continue along SAVED originalNext, not the mutated next. Reaching the original tail identifies the new head. Verify its prev is null and the original head’s new next is null; changing only next would leave backward traversal broken.

Brute force and the improvement

Save all original NODE REFERENCES in a list, then reconnect each node’s next and prev in the reverse order. This uses O(n) time and O(n) extra reference storage; copying only values into new nodes would not preserve node identity. Swapping each existing node’s two links avoids the list. The recursive version still uses O(n) call-stack space; the iterative version below achieves O(n) time and O(1) extra space and is preferable for a long list.

Intuition: old previous becomes new next

Originally 10.next points to 20 and 20.prev points to 10. After reversal, 20 must point forward to 10 and 10 must point backward to 20. Exchange next and prev at every node.

The danger is traversal: after exchanging links, current.next points toward the old predecessor. Save the original next link first and continue along that saved link.

The original tail is the new head. Its old next is null, so its new prev becomes null. Similarly, the old head’s new next becomes null, giving the correct new tail.

Algorithm

  1. Stop and return null for an empty list.
  2. Save current.next as originalNext.
  3. Set current.next to its old prev, and current.prev to originalNext.
  4. If originalNext is null, return this original tail as the new head.
  5. Otherwise reverse the remaining original forward chain and return its head.

Java solution

The recursive and iterative methods exchange the same two links at each node. Prefer the iterative method for a long list: it avoids both stack growth and stack-overflow risk.

Java
import java.util.*;

class Solution {
    public static final class DllNode {
        public int data; public DllNode prev, next; // A node has TWO links to maintain.
        public DllNode(int value) { data = value; }
    }
    public static DllNode reverseDLL(DllNode head) {
        if (head == null) return null; // Defensive empty-list behavior.
        DllNode originalNext = head.next; // Save the original forward link BEFORE exchanging links.
        head.next = head.prev; // Old predecessor becomes the new successor.
        head.prev = originalNext; // Old successor becomes the new predecessor.
        if (originalNext == null) return head; // Old tail is the new head, with prev == null.
        return reverseDLL(originalNext); // Continue along the ORIGINAL forward path.
    }
    public static DllNode reverseDLLIterative(DllNode head) {
        DllNode newHead = null;
        while (head != null) { // Prefer this for long lists: Java does not eliminate tail calls.
            DllNode originalNext = head.next;
            head.next = head.prev; head.prev = originalNext; // Same per-node exchange as recursion.
            newHead = head; head = originalNext; // Remember the latest node and follow the saved link.
        }
        return newHead; // Null for empty input; original tail otherwise.
    }

    public static void main(String[] args) {
        DllNode first = new DllNode(10), middle = new DllNode(20), last = new DllNode(30);
        first.next = middle; middle.prev = first; middle.next = last; last.prev = middle;
        DllNode newHead = reverseDLL(first); // Prefer reverseDLLIterative for a long list.
        for (DllNode node = newHead; node != null; node = node.next) {
            System.out.print(node.data + " "); // 30 20 10
        }
    }
}

The driver builds 10⇄20⇄30 and prints 30 20 10. Its setup/display loop is outside the recursive reversal. A one-node list remains the same node with both links null.

Pointer changes and dry run

Numbered illustrated dry run for Reverse a Doubly Linked List; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: 10 ⇄ 20 ⇄ 30; head = node 10

What to track: Track head, originalNext, and both links of the node being processed. Labels 10/20/30 identify node objects, not copied values.

  1. Save the original forward link

    Java operationDllNode originalNext = head.next;
    Statehead = 10; originalNext = 20; old prev = null; old next = 20

    The saved reference tells recursion where to go after this node’s links are exchanged.

  2. Exchange the first node’s links

    Java operationhead.next = head.prev;
    Stateafter both assignments: 10.next = null; 10.prev = 20

    head.prev = originalNext finishes the exchange. Following head.next now would stop immediately, so the code must follow originalNext instead.

  3. Process the middle node

    Java operationreturn reverseDLL(originalNext);
    Statechild head = 20; saved originalNext = 30; after exchange: 20.next = 10; 20.prev = 30

    This child still knows the old successor even though its new next points backward.

  4. Recognize the old tail

    Java operationif (originalNext == null) return head;
    Stateat node 30: originalNext = null; after exchange: 30.next = 20; 30.prev = null

    The old tail is the new head. Returning before the exchange would leave its links wrong.

  5. Propagate the same head

    Java operationreturn reverseDLL(originalNext);
    Statenode 30 returns through the node-20 and node-10 frames; wrapper receives node 30

    There is no undo: reversing is the intended mutation. Both directions are checked, not only the forward traversal.

Final result: new head = node 30; forward 30→20→10; backward 10→20→30.

Current node Saved original next New next New prev
10 20 null 20
20 30 10 30
30 null 20 null

The recursive calls follow 10→20→30 along the saved original links. The final call returns node 30; each waiting caller returns that same reference upward. Following the newly assigned next links from 30 now visits 20 then 10.

During partial reversal, mixed old/new links are not yet a complete traversable list. Inspect the final structure, not a prematurely followed path halfway through mutation.

Why it works

For every original edge A.next=B and B.prev=A, exchanging both endpoints produces B.next=A and A.prev=B. All nodes are visited exactly once along the saved original forward chain. Returning the old tail therefore gives the head of a fully reversed list with correct endpoints and unchanged node identities.

Complexity and alternative approaches

Both methods take O(n) time. Recursion uses O(n) auxiliary stack space. Iteration uses O(1) auxiliary space and creates no replacement nodes.

Java does not guarantee tail-call elimination. A deep call chain can throw StackOverflowError long before the published maximum; do not claim the recursive method is safe for one million nodes. Changing the JVM stack size is not a reliable algorithmic fix for a judge.

An extra stack of node references can also reverse traversal but consumes O(n) space unnecessarily. Rebuilding a new list changes identities, and swapping data rather than links fails the in-place structural contract.

Common mistakes

  • Following current.next after swapping, which walks in the wrong direction.
  • Updating only next and leaving prev inconsistent.
  • Returning the old head.
  • Testing only repeated displayed values, which can hide identity/order errors.
  • Reporting O(1) space for the recursive implementation.

Practice next

Next lessonprinting an immutable list backward

Back to Recursion and backtracking →