Reverse a doubly linked list

Solution: Swap Pointers

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

Step-by-Step Example

Original list: 1 <-> 2 <-> 3

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

Alternative: Three Pointer Approach

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
}

Comparison with Singly Linked List

Edge Cases

• Empty list: Return null
• Single node: After swap, node points to null both ways. Return same node.
• Two nodes: Swap works correctly, returns second node as new head

Complexity

Time: O(n) - single pass through list
Space: O(1) - only a few pointers

Common Mistakes

• Moving to current.next: After swap, next is in prev field!
• Not updating newHead: Need to track last processed node
• Forgetting to swap prev: Must swap both pointers, not just next
• Not handling null head: Check for null at start

Related Problems

• Linked List - Linked list operations
• Find Out if a Linked List has a Cycle - Linked list algorithms
• Check if a Linked list is a Palindrome or Not - Pointer manipulation