Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Reverse a Doubly Linked List

Problem Statement

Write a Java program that reverses a doubly linked list. The doubly linked list consists of nodes, each containing an integer value, a reference to the next node, and a reference to the previous node. The program should reverse the order of the nodes (e.g., 1↔2↔3 becomes 3↔2↔1) by swapping the next and prev pointers of each node and updating the head. Test the implementation with doubly linked lists of varying sizes, including empty lists, single-node lists, and multi-node lists. You can visualize this as rearranging a chain of numbered cards, flipping their order so the last card becomes the first, with each card linked to both its predecessor and successor.

Input:

  • A doubly linked list of integers (e.g., 1↔2↔3↔4). Output: The reversed doubly linked list as a string in forward order (e.g., "4 3 2 1"). Constraints:
  • The list size is between 0 and 10^5.
  • Node values are integers in the range [-10^9, 10^9].
  • The list may be empty. Example:
  • Input: 1↔2↔3↔4
  • Output: "4 3 2 1"
  • Explanation: The list 1↔2↔3↔4 is reversed to 4↔3↔2↔1.
  • Input: []
  • Output: "[]"
  • Explanation: An empty list remains empty.
  • Input: 5
  • Output: "5"
  • Explanation: A single-node list is unchanged.

Pseudocode

CLASS DoublyNode
    SET value to integer
    SET next to DoublyNode (null by default)
    SET prev to DoublyNode (null by default)
ENDCLASS

FUNCTION reverseList(head)
    IF head is null THEN
        RETURN null
    ENDIF
    SET current to head
    SET newHead to null
    WHILE current is not null
        SET temp to current.prev
        SET current.prev to current.next
        SET current.next to temp
        SET newHead to current
        SET current to current.prev
    ENDWHILE
    RETURN newHead
ENDFUNCTION

FUNCTION toString(head)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    WHILE current is not null
        APPEND current.value to result
        IF current.next is not null THEN
            APPEND " " to result
        ENDIF
        SET current to current.next
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of doubly linked lists
    FOR each testCase in testCases
        PRINT test case details
        CALL reverseList(testCase.head)
        PRINT reversed list using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a DoublyNode class with: a. An integer value. b. A next pointer to the next node. c. A prev pointer to the previous node.
  2. In reverseList: a. If head is null, return null (empty list). b. Initialize current to head, newHead to track the new head. c. While current is not null:
    • Swap current.prev and current.next.
    • Update newHead to current (last node processed becomes head).
    • Move current to the next node (now in prev due to swap). d. Return newHead.
  3. In toString: a. If head is null, return "[]". b. Traverse the list forward, append each value to a StringBuilder with spaces. c. Return the string representation.
  4. In main, test with empty, single-node, and multi-node doubly linked lists.

Java Implementation

public class ReverseDoublyLinkedList {
    // Node class for the doubly linked list
    static class DoublyNode {
        int value;
        DoublyNode next;
        DoublyNode prev;

        DoublyNode(int value) {
            this.value = value;
            this.next = null;
            this.prev = null;
        }
    }

    // Reverses the doubly linked list
    public DoublyNode reverseList(DoublyNode head) {
        if (head == null) {
            return null;
        }
        DoublyNode current = head;
        DoublyNode newHead = null;
        while (current != null) {
            // Swap prev and next pointers
            DoublyNode temp = current.prev;
            current.prev = current.next;
            current.next = temp;
            // Update newHead to current node (last node processed)
            newHead = current;
            // Move to next node (now in prev due to swap)
            current = current.prev;
        }
        return newHead;
    }

    // Converts doubly linked list to string for output
    public String toString(DoublyNode head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        DoublyNode current = head;
        while (current != null) {
            result.append(current.value);
            if (current.next != null) {
                result.append(" ");
            }
            current = current.next;
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        DoublyNode head;

        TestCase(int[] values) {
            if (values.length == 0) {
                head = null;
                return;
            }
            head = new DoublyNode(values[0]);
            DoublyNode current = head;
            for (int i = 1; i < values.length; i++) {
                DoublyNode newNode = new DoublyNode(values[i]);
                newNode.prev = current;
                current.next = newNode;
                current = newNode;
            }
        }
    }

    // Main method to test doubly linked list reversal
    public static void main(String[] args) {
        ReverseDoublyLinkedList reverser = new ReverseDoublyLinkedList();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{1, 2, 3, 4}), // Multi-node list
            new TestCase(new int[]{}),           // Empty list
            new TestCase(new int[]{5}),          // Single node
            new TestCase(new int[]{1, 1, 1}),    // List with duplicates
            new TestCase(new int[]{10, 20})      // Two nodes
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            TestCase test = testCases[i];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input list: " + reverser.toString(test.head));
            DoublyNode reversed = reverser.reverseList(test.head);
            System.out.println("Reversed list: " + reverser.toString(reversed) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input list: 1 2 3 4
Reversed list: 4 3 2 1

Test case 2:
Input list: []
Reversed list: []

Test case 3:
Input list: 5
Reversed list: 5

Test case 4:
Input list: 1 1 1
Reversed list: 1 1 1

Test case 5:
Input list: 10 20
Reversed list: 20 10

Explanation:

  • Test case 1: Reverses 1↔2↔3↔4 to 4↔3↔2↔1.
  • Test case 2: Empty list remains empty.
  • Test case 3: Single node 5 is unchanged.
  • Test case 4: List with duplicates 1↔1↔1 reverses to 1↔1↔1.
  • Test case 5: Two nodes 10↔20 reverse to 20↔10.

How It Works

  • DoublyNode: Stores an integer value, a next pointer, and a prev pointer.
  • reverseList:
    • Returns null for empty lists.
    • Iteratively swaps prev and next pointers for each node.
    • Tracks the new head (last node processed).
    • Moves to the next node using the swapped prev pointer.
  • toString: Converts the list to a space-separated string, traversing forward, returning "[]" for empty lists.
  • Example Trace (Test case 1):
    • Input: 1↔2↔3↔4.
    • Initial: current=1, newHead=null.
    • Step 1: 1(next=null,prev=2), newHead=1, current=2.
    • Step 2: 2(next=1,prev=3), newHead=2, current=3.
    • Step 3: 3(next=2,prev=4), newHead=3, current=4.
    • Step 4: 4(next=3,prev=null), newHead=4, current=null.
    • Return: 4↔3↔2↔1.
  • Main Method: Tests multi-node, empty, single-node, duplicate, and two-node lists.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Reverse ListO(n)O(1)
To StringO(n)O(n)

Note:

  • n is the number of nodes in the list.
  • Time complexity: O(n) for reverseList (single pass); O(n) for toString (traverse list).
  • Space complexity: O(1) for reverseList (constant pointers); O(n) for toString (StringBuilder).
  • Worst case: O(n) time, O(n) space for output with large lists.

✅ Tip: In a doubly linked list, reversing is simplified by swapping next and prev pointers. Always update the head to the last node processed to maintain the list structure.

⚠ Warning: Carefully swap next and prev pointers to avoid losing references. Ensure null checks for edge cases like empty or single-node lists.