Reverse a Doubly Linked List: Iterative, Recursive, and Common Mistakes

Reverse a Doubly Linked List: Iterative, Recursive, and the Common Mistakes

Reversing a doubly linked list (DLL) is a classic interview question that tests pointer manipulation under more constraints than the singly-linked variant. Each node has both prev and next pointers, and a correct reversal swaps both pointers at every node while updating the head reference. The base problem is simple in concept but easy to get wrong under pressure — most candidates trip on either pointer order or the head update. This guide covers the iterative and recursive approaches with working code and the mistakes that show up in interviews.

Problem Statement

Given the head of a doubly linked list, reverse it in place and return the new head. Each node has val, prev, and next; the original head becomes the new tail.

Examples:

• Input: 1 ⇄ 2 ⇄ 3 ⇄ 4 → Output: 4 ⇄ 3 ⇄ 2 ⇄ 1
• Input: empty list → Output: empty list
• Input: single node → unchanged

Approach 1: Iterative Pointer Swap (Standard Answer)

Walk the list, swapping prev and next at each node. The “next” node before the swap becomes the next iteration’s target. After processing the last node, return it as the new head.

class DLLNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next


def reverse_dll(head: DLLNode) -> DLLNode:
    """O(n) time, O(1) space."""
    current = head
    new_head = head

    while current:
        # Swap prev and next pointers
        current.prev, current.next = current.next, current.prev
        new_head = current
        # Advance: original next is now in current.prev
        current = current.prev

    return new_head


# Test helper to print the list forward and backward
def to_forward(head):
    result = []
    while head:
        result.append(head.val)
        if not head.next:
            tail = head
        head = head.next
    return result, tail

def to_backward(tail):
    result = []
    while tail:
        result.append(tail.val)
        tail = tail.prev
    return result


# Build 1 ⇄ 2 ⇄ 3 ⇄ 4
nodes = [DLLNode(i) for i in range(1, 5)]
for i in range(3):
    nodes[i].next = nodes[i+1]
    nodes[i+1].prev = nodes[i]

new_head = reverse_dll(nodes[0])
fwd, tail = to_forward(new_head)
bwd = to_backward(tail)
print(fwd)  # [4, 3, 2, 1]
print(bwd)  # [1, 2, 3, 4]

Complexity: O(n) time, O(1) extra space.

Why the swap-then-advance pattern works: after we swap prev and next on the current node, the original next direction is preserved in current.prev (since we swapped). So we advance via current.prev, which is the original next.

Approach 2: Recursive Reversal

Recurse to the end, then unwind, swapping pointers as the call stack unwinds. O(n) stack space; useful when the interviewer asks for a recursive variant.

def reverse_dll_recursive(head: DLLNode) -> DLLNode:
    """O(n) time, O(n) stack space."""
    if not head:
        return None

    # Swap this node's pointers
    head.prev, head.next = head.next, head.prev

    # If head.prev (original next) is None, we're at the new head
    if not head.prev:
        return head

    # Recurse on the original next (now in head.prev)
    return reverse_dll_recursive(head.prev)

Same time complexity; uses recursion stack space proportional to list length. For very long lists, prefer the iterative version.

Approach 3: Two-Pointer Walk (Alternative)

Use a temporary variable to remember the original next, then swap and advance. Conceptually equivalent to Approach 1 but spelled out more explicitly.

def reverse_dll_explicit(head: DLLNode) -> DLLNode:
    """O(n) time, O(1) space — explicit temp variable."""
    current = head
    new_head = None

    while current:
        # Save original next
        next_node = current.next
        # Swap prev and next
        current.next = current.prev
        current.prev = next_node
        # Track the new head (the last node we processed)
        new_head = current
        # Advance to the original next
        current = next_node

    return new_head

Some find this version easier to reason about because the temp variable makes the original next explicit. Pick whichever style feels cleaner; both are O(n) time and O(1) space.

Common Mistakes

• Forgetting to update both pointers. Reversing only next while leaving prev alone produces a broken list — backwards traversal fails. Always swap both at every node.
• Losing track of the new head. The new head is the last node visited (the original tail). Track it explicitly with a variable; don’t try to compute it after the loop.
• Advancing in the wrong direction. After swapping, the original next direction is in current.prev. Advancing via current.next goes backward — toward already-processed nodes — and the loop terminates incorrectly.
• Returning the original head. The original head becomes the new tail. Return the new head (last node visited), not head.
• Not handling empty list and single-node cases. The standard implementation handles these via the loop condition (empty: loop body doesn’t execute; single node: one swap, no advance), but bugs in the head-tracking can manifest in these edge cases. Test them.
• Memory issues with mutual references. In garbage-collected languages, mutual prev/next references aren’t a concern. In manual-memory languages (C, C++ without smart pointers), the reversal mutates pointers in place — no allocation needed, no leaks possible from the algorithm itself.

Common Variations

Reverse a singly linked list

(LeetCode #206) The simpler variant. Only one pointer per node; same iterative pattern with one swap per node.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse_singly(head: ListNode) -> ListNode:
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

Reverse in groups of k

(LeetCode #25 — Reverse Nodes in k-Group) Reverse the first k nodes, then the next k, and so on. Apply the standard reversal to each group, stitching them together.

Reverse between positions m and n

(LeetCode #92) Reverse a sub-segment of the list. Walk to position m, reverse n-m nodes, reconnect to the surrounding nodes.

Check if a linked list is a palindrome

(LeetCode #234) Uses the singly-linked reversal as a subroutine: reverse the second half, compare to first half. See our palindrome guide.

Detect and remove cycles

If the DLL has a cycle (some node’s next points back to an earlier node), the reversal algorithm above doesn’t terminate. Detect cycles first via Floyd’s algorithm, or assume well-formed input.

Frequently Asked Questions

See also: Check if a Linked List is a Palindrome • Detect a Cycle in a Linked List • Serialize and Deserialize a Binary Tree

Original: 1 <-> 2 <-> 3 <-> 4
Reversed: 4 <-> 3 <-> 2 <-> 1

class Node {
    constructor(val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

function reverseDoublyLinkedList(head) {
    if (head === null) return null;

    let current = head;
    let newHead = null;

    while (current !== null) {
        // Swap prev and next for current node
        let temp = current.prev;
        current.prev = current.next;
        current.next = temp;

        // Update new head (will be the last node we process)
        newHead = current;

        // Move to next node (which is now in prev due to swap)
        current = current.prev;
    }

    return newHead;
}

// Helper to create doubly linked list
function createDoublyLinkedList(arr) {
    if (arr.length === 0) return null;

    const head = new Node(arr[0]);
    let current = head;

    for (let i = 1; i < arr.length; i++) {
        const newNode = new Node(arr[i]);
        current.next = newNode;
        newNode.prev = current;
        current = newNode;
    }

    return head;
}

// Helper to print list forward
function printForward(head) {
    const arr = [];
    while (head) {
        arr.push(head.val);
        head = head.next;
    }
    console.log(arr.join(" <-> "));
}

// Helper to print list backward
function printBackward(tail) {
    const arr = [];
    while (tail) {
        arr.push(tail.val);
        tail = tail.prev;
    }
    console.log(arr.join(" <-> "));
}

// Test
const list = createDoublyLinkedList([1, 2, 3, 4, 5]);
console.log("Original:");
printForward(list);  // 1 <-> 2 <-> 3 <-> 4 <-> 5

const reversed = reverseDoublyLinkedList(list);
console.log("Reversed:");
printForward(reversed);  // 5 <-> 4 <-> 3 <-> 2 <-> 1

Initial state:
  null <- 1 <-> 2 <-> 3 -> null

Process node 1:
  Swap: 1.prev = 2, 1.next = null
  newHead = 1
  current = 1.prev = 2

Process node 2:
  Swap: 2.prev = 3, 2.next = 1
  newHead = 2
  current = 2.prev = 3

Process node 3:
  Swap: 3.prev = null, 3.next = 2
  newHead = 3
  current = 3.prev = null (done)

Result: null <- 3 <-> 2 <-> 1 -> null
Return newHead = 3

function reverseDoublyLinkedListThreePtr(head) {
    if (head === null) return null;

    let prev = null;
    let current = head;

    while (current !== null) {
        let next = current.next;

        // Reverse both pointers
        current.next = prev;
        current.prev = next;

        // Move forward
        prev = current;
        current = next;
    }

    return prev;  // New head
}