Reverse a Doubly Linked List in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after reversing this doubly linked list?

Given the doubly linked list: 1 <-> 2 <-> 3 <-> 4 <-> null, what is the printed list after applying the reverse function?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
    Node head;

    void reverse() {
        Node temp = null;
        Node current = head;
        while (current != null) {
            temp = current.prev;
            current.prev = current.next;
            current.next = temp;
            current = current.prev;
        }
        if (temp != null) {
            head = temp.prev;
        }
    }

    void printList() {
        Node node = head;
        while (node != null) {
            System.out.print(node.data + " <-> ");
            node = node.next;
        }
        System.out.println("null");
    }
}

DoublyLinkedList dll = new DoublyLinkedList();
dll.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
dll.head.next = second; second.prev = dll.head;
second.next = third; third.prev = second;
third.next = fourth; fourth.prev = third;

dll.reverse();
dll.printList();

A 1 <-> 2 <-> 3 <-> 4 <-> null

B 4 <-> 3 <-> 2 <-> null

C 4 <-> 3 <-> 2 <-> 1 <-> null

D null

💡 Hint

Think about swapping the prev and next pointers for each node.

The reverse function swaps the prev and next pointers for each node and then updates the head to the last node processed. This reverses the list order.

❓ Predict Output

intermediate

What is the output of this reverse function on a single-node list?

Given a doubly linked list with only one node (5 <-> null), what is the output after calling reverse() and then printList()?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
    Node head;

    void reverse() {
        Node temp = null;
        Node current = head;
        while (current != null) {
            temp = current.prev;
            current.prev = current.next;
            current.next = temp;
            current = current.prev;
        }
        if (temp != null) {
            head = temp.prev;
        }
    }

    void printList() {
        Node node = head;
        while (node != null) {
            System.out.print(node.data + " <-> ");
            node = node.next;
        }
        System.out.println("null");
    }
}

DoublyLinkedList dll = new DoublyLinkedList();
dll.head = new Node(5);

dll.reverse();
dll.printList();

A 5 <-> null

B null

C 5

D null <-> 5

💡 Hint

Reversing a single node list should not change the list.

Since there is only one node, reversing swaps prev and next which are both null, so the list remains the same.

🔧 Debug

advanced

Why does this reverse function fail to update the head correctly?

Consider this reverse function for a doubly linked list. After reversal, the list prints empty. What is the bug?

DSA Java

void reverse() {
    Node temp = null;
    Node current = head;
    while (current != null) {
        temp = current.prev;
        current.prev = current.next;
        current.next = temp;
        current = current.prev;
    }
    head = temp;
}

A head should be assigned to temp.prev, not temp

B The loop should use current.next instead of current.prev

C temp should be initialized to head, not null

D The function should not swap prev and next pointers

💡 Hint

Check how head is updated after the loop.

After the loop, temp points to the previous node of the last processed node, so head must be set to temp.prev to point to the new first node.

🧠 Conceptual

advanced

What is the time complexity of reversing a doubly linked list?

If a doubly linked list has n nodes, what is the time complexity of reversing it by swapping prev and next pointers?

A O(n^2)

B O(n)

C O(log n)

D O(1)

💡 Hint

Consider how many nodes you visit and update.

Each node is visited once and pointers are swapped, so the operation is linear in the number of nodes.

❓ Predict Output

expert

What is the output after reversing this doubly linked list with duplicate values?

Given the doubly linked list: 2 <-> 3 <-> 3 <-> 5 <-> null, what is the printed list after applying the reverse function?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
    Node head;

    void reverse() {
        Node temp = null;
        Node current = head;
        while (current != null) {
            temp = current.prev;
            current.prev = current.next;
            current.next = temp;
            current = current.prev;
        }
        if (temp != null) {
            head = temp.prev;
        }
    }

    void printList() {
        Node node = head;
        while (node != null) {
            System.out.print(node.data + " <-> ");
            node = node.next;
        }
        System.out.println("null");
    }
}

DoublyLinkedList dll = new DoublyLinkedList();
dll.head = new Node(2);
Node second = new Node(3);
Node third = new Node(3);
Node fourth = new Node(5);
dll.head.next = second; second.prev = dll.head;
second.next = third; third.prev = second;
third.next = fourth; fourth.prev = third;

dll.reverse();
dll.printList();

A null

B 2 <-> 3 <-> 3 <-> 5 <-> null

C 5 <-> 3 <-> 2 <-> null

D 5 <-> 3 <-> 3 <-> 2 <-> null

💡 Hint

Duplicates do not affect the reversal logic.

The reverse function swaps pointers for all nodes, reversing the order including duplicates.

Practice

1. What is the main purpose of reversing a doubly linked list?

easy

A. To change the direction of traversal so the last node becomes the first

B. To delete all nodes from the list

C. To sort the nodes in ascending order

D. To convert it into a singly linked list

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes with pointers to both previous and next nodes, allowing traversal in both directions.

2. Step 2: Purpose of reversing

   Reversing swaps the previous and next pointers of each node, making the last node the first and vice versa.

3. Final Answer:

   To change the direction of traversal so the last node becomes the first -> Option A

4. Quick Check:

   Reversing means swapping directions [OK]

Hint: Reversing flips the list direction, last becomes first [OK]

Common Mistakes:

• Confusing reversing with deleting nodes
• Thinking reversing sorts the list
• Assuming it converts to singly linked list

2. Which of the following Java code snippets correctly swaps the next and prev pointers of a node curr in a doubly linked list?

easy

A. curr.next = curr.prev; curr.prev = null;

B. Node temp = curr.prev; curr.prev = curr.next; curr.next = null;

C. curr.next = curr.prev; curr.prev = curr.next;

D. Node temp = curr.next; curr.next = curr.prev; curr.prev = temp;

Solution

1. Step 1: Identify correct swapping logic

   Swapping two pointers requires a temporary variable to hold one pointer before overwriting it.

2. Step 2: Check each option

   A temporary variable is required to swap pointers without data loss. curr.next = curr.prev; curr.prev = null; incorrectly sets prev to null. Node temp = curr.prev; curr.prev = curr.next; curr.next = null; uses temp but wrongly sets next to null. curr.next = curr.prev; curr.prev = curr.next; overwrites without preserving original values. Node temp = curr.next; curr.next = curr.prev; curr.prev = temp; correctly swaps the pointers.

3. Final Answer:

   Node temp = curr.next; curr.next = curr.prev; curr.prev = temp; -> Option D

4. Quick Check:

   Use temp variable to swap pointers [OK]

Hint: Always use a temp variable to swap two pointers [OK]

Common Mistakes:

• Swapping without a temporary variable
• Setting one pointer to null accidentally
• Swapping pointers in wrong order

3. Given the following doubly linked list nodes and code to reverse it, what will be the printed output after reversal?

class Node {
  int data;
  Node prev, next;
  Node(int d) { data = d; prev = next = null; }
}

// List: 1 <-> 2 <-> 3
Node head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
head.next = second; second.prev = head;
second.next = third; third.prev = second;

// Reverse code snippet
Node curr = head;
Node temp = null;
while (curr != null) {
  temp = curr.prev;
  curr.prev = curr.next;
  curr.next = temp;
  curr = curr.prev;
}
if (temp != null) head = temp.prev;

// Print list forward
Node ptr = head;
while (ptr != null) {
  System.out.print(ptr.data + " ");
  ptr = ptr.next;
}

medium

A. 1 2 3

B. 3 2 1

C. 3 1 2

D. 2 3 1

Solution

1. Step 1: Understand reversal logic

   The code swaps prev and next for each node, then moves curr to the original next node (now prev after swap).

2. Step 2: Trace the list after reversal

   Original list: 1 <-> 2 <-> 3
   After reversal, head points to node with data 3.
   Printing from head forward prints: 3 2 1

3. Final Answer:

   3 2 1 -> Option B

4. Quick Check:

   Reversed list prints nodes backward [OK]

Hint: After reversal, head points to original tail node [OK]

Common Mistakes:

• Not updating head after reversal
• Confusing prev and next pointers
• Printing from old head instead of new head

4. Identify the error in the following code snippet that attempts to reverse a doubly linked list:

Node curr = head;
while (curr != null) {
  Node temp = curr.next;
  curr.next = curr.prev;
  curr.prev = temp;
  curr = curr.next;
}

medium

A. The pointers next and prev are not swapped correctly

B. The temp variable should store curr.prev, not curr.next

C. The loop moves curr to curr.next instead of curr.prev after swapping

D. The loop condition should be curr.next != null

Solution

1. Step 1: Analyze pointer swapping

   The code swaps next and prev correctly using temp.

2. Step 2: Check loop iteration step

   After swapping, curr.next points to the original prev. To move forward in the original list, curr should move to curr.prev (which is original next). The code incorrectly moves to curr.next, causing wrong traversal.

3. Final Answer:

   The loop moves curr to curr.next instead of curr.prev after swapping -> Option C

4. Quick Check:

   Move curr to curr.prev after swapping [OK]

Hint: After swapping, move curr to curr.prev to continue traversal [OK]

Common Mistakes:

• Moving curr to wrong pointer after swap
• Confusing temp usage
• Incorrect loop condition

5. You have a doubly linked list with nodes containing integer data. After reversing the list using the standard pointer swap method, you want to find the middle node efficiently. Which approach is best to find the middle node after reversal?

hard

A. Use two pointers starting from the new head: one moves one step, the other moves two steps until the faster reaches null

B. Traverse from the original head before reversal to find the middle

C. Count nodes from the tail and divide by two to find middle index

D. Reverse the list again and then find the middle node

Solution

1. Step 1: Understand list reversal effect

   After reversal, the head points to the original tail. The list is still doubly linked and can be traversed forward.

2. Step 2: Efficient middle node finding

   The two-pointer technique (slow and fast pointers) starting from the new head finds the middle in one pass efficiently.

3. Final Answer:

   Use two pointers starting from the new head: one moves one step, the other moves two steps until the faster reaches null -> Option A

4. Quick Check:

   Two-pointer method finds middle in O(n) [OK]

Hint: Use slow and fast pointers from new head to find middle [OK]

Common Mistakes:

• Trying to find middle from old head after reversal
• Counting nodes from tail which is inefficient
• Reversing list again unnecessarily