Reverse a Doubly Linked List in DSA C#

Mental Model

To reverse a doubly linked list, we swap the previous and next pointers of each node, then update the head to the last node.

Analogy: Imagine a train with cars connected front and back. Reversing means flipping the direction of all connections so the last car becomes the first.

null ← 1 ↔ 2 ↔ 3 -> null
↑head

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, reverse the list

Goal: Reverse the list so it becomes 3 ↔ 2 ↔ 1

Step 1: Start at head (node 1), swap its prev and next pointers

null ← 1 ↔ null  2 ↔ 3 -> null
↑curr at 1

Why: Swapping pointers reverses the direction of links for the current node

Step 2: Move curr to previous node (which was next before swap), now node 2

null ← 1 null  2 ↔ 3 -> null
↑curr at 2

Why: After swapping, prev points to next node, so move curr there to continue

Step 3: Swap prev and next pointers of node 2

null ← 1 null  2 ↔ null  3 -> null
↑curr at 2

Why: Reverse links for node 2 to continue reversing the list

Step 4: Move curr to previous node (which was next before swap), now node 3

null ← 1 null  2 null  3 -> null
↑curr at 3

Why: Continue traversal using swapped pointers

Step 5: Swap prev and next pointers of node 3

null ← 1 null  2 null  3 -> null
↑curr at 3

Why: Reverse links for last node

Step 6: Move curr to previous node (which was next before swap), now null

null ← 1 null  2 null  3 -> null
↑curr at null

Why: Reached end of original list, stop

Step 7: Update head to last processed node (node 3)

null ← 3 ↔ 2 ↔ 1 -> null
↑head

Why: New head is the last node processed after reversal

Result:

null ← 3 ↔ 2 ↔ 1 -> null
↑head

Annotated Code

DSA C#

using System;

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

class DoublyLinkedList {
    public Node head;

    public void Append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = newNode;
        newNode.prev = curr;
    }

    public void Reverse() {
        Node curr = head;
        Node temp = null;
        while (curr != null) {
            // Swap prev and next
            temp = curr.prev;
            curr.prev = curr.next;
            curr.next = temp;
            // Move curr to prev (which is original next)
            curr = curr.prev;
        }
        // After loop, temp is at previous node, so update head
        if (temp != null) {
            head = temp.prev;
        }
    }

    public void PrintList() {
        Node curr = head;
        while (curr != null) {
            Console.Write(curr.data);
            if (curr.next != null) Console.Write(" ↔ ");
            curr = curr.next;
        }
        Console.WriteLine();
    }
}

class Program {
    static void Main() {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.Append(1);
        dll.Append(2);
        dll.Append(3);
        dll.PrintList();
        dll.Reverse();
        dll.PrintList();
    }
}

while (curr != null) {

iterate through each node to reverse pointers

temp = curr.prev;

store original prev pointer temporarily

curr.prev = curr.next;

swap prev and next pointers to reverse link direction

curr.next = temp;

complete pointer swap for current node

curr = curr.prev;

move to next node in original order using swapped pointers

if (temp != null) { head = temp.prev; }

update head to new first node after reversal

Output

1 ↔ 2 ↔ 3

3 ↔ 2 ↔ 1

Complexity Analysis

Time: O(n) because we visit each node once to swap pointers

Space: O(1) because we only use a few extra variables for swapping

vs Alternative: Compared to creating a new reversed list (O(n) time and space), this reverses in place with no extra space

Edge Cases

empty list

Reverse does nothing, list remains empty

DSA C#

while (curr != null) {

single node list

Reverse swaps pointers but list stays the same

DSA C#

while (curr != null) {

When to Use This Pattern

When you see a problem asking to reverse a doubly linked list, reach for pointer swapping because it reverses links in place efficiently.

Common Mistakes

Mistake: Not swapping both prev and next pointers for each node
Fix: Always swap prev and next pointers together to correctly reverse links

Mistake: Not updating the head pointer after reversal
Fix: Update head to the last processed node after the loop ends

Summary

Reverses a doubly linked list by swapping each node's prev and next pointers.

Use when you need to reverse the order of nodes in a doubly linked list efficiently.

The key insight is that swapping prev and next pointers for each node reverses the list direction.

Practice

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

easy

A. To change the order of nodes so the last becomes first and vice versa

B. To delete all nodes from the list

C. To add new nodes at the end of the list

D. To sort the nodes in ascending order

Solution

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

   A doubly linked list has nodes connected forward and backward using next and prev pointers.

2. Step 2: Purpose of reversing

   Reversing swaps the direction so the last node becomes the first and the first becomes the last.

3. Final Answer:

   To change the order of nodes so the last becomes first and vice versa -> Option A

4. Quick Check:

   Reversing = changing node order [OK]

Hint: Reversing flips the list order front to back [OK]

Common Mistakes:

• Confusing reversing with deleting nodes
• Thinking reversing sorts the list
• Mixing up adding nodes with reversing

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

easy

A. node.next = node.prev; node.prev = node.next;

B. node.prev = node.next; node.next = node.prev;

C. var temp = node.prev; node.next = node.prev; node.prev = temp;

D. var temp = node.next; node.next = node.prev; node.prev = temp;

Solution

1. Step 1: Understand swapping pointers

   To swap two pointers, use a temporary variable to hold one value before overwriting it.

2. Step 2: Check each option

   The correct snippet saves node.next in temp, assigns node.next = node.prev, then node.prev = temp. Direct assignments without temp cause data loss. The flawed temp usage assigns node.next = node.prev without saving the original node.next first, losing data.

3. Final Answer:

   var temp = node.next; node.next = node.prev; node.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
• Assigning pointers in wrong order
• Confusing next and prev roles

3. What will be the output of the following C# code after reversing the doubly linked list?

class Node {
  public int data;
  public Node next, prev;
  public Node(int d) { data = d; next = prev = 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 function
Node Reverse(Node head) {
  Node current = head;
  Node temp = null;
  while (current != null) {
    temp = current.prev;
    current.prev = current.next;
    current.next = temp;
    current = current.prev;
  }
  if (temp != null) head = temp.prev;
  return head;
}

head = Reverse(head);

// Print list forward
Node tempNode = head;
string result = "";
while (tempNode != null) {
  result += tempNode.data + " -> ";
  tempNode = tempNode.next;
}
result += "null";
Console.WriteLine(result);

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. null

D. 1 -> 3 -> 2 -> null

Solution

1. Step 1: Trace the reversal loop

   Each node swaps its next and prev pointers. The loop moves current to current.prev (which was originally next). After the loop, head is updated to the last processed node.

2. Step 2: Verify the new order

   Original list: 1 <-> 2 <-> 3. After reversal, the list becomes 3 <-> 2 <-> 1. Printing forward from new head prints 3 -> 2 -> 1 -> null.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option A

4. Quick Check:

   Reversed list prints backward order [OK]

Hint: Reversing flips list order; last node becomes head [OK]

Common Mistakes:

• Not updating head after reversal
• Confusing next and prev pointers
• Printing list without updating head

4. Identify the bug in this reverse function for a doubly linked list:

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

medium

A. The variable temp should store current.next, not current.prev

B. The loop should move current to current.prev, not current.next

C. The head update line should be head = temp.next

D. There is no bug; the code is correct

Solution

1. Step 1: Analyze pointer swapping

   The code swaps next and prev pointers correctly, but moves current to current.next, which after swapping points backward.

2. Step 2: Correct traversal direction

   After swapping, current should move to current.prev (originally next) to continue forward traversal. Moving to current.next causes skipping or infinite loop.

3. Final Answer:

   The loop should move current to current.prev, not current.next -> Option B

4. Quick Check:

   Traverse using swapped pointers correctly [OK]

Hint: After swapping, move current to current.prev pointer [OK]

Common Mistakes:

• Moving current in wrong direction after swap
• Incorrect temp assignment
• Wrong head update after reversal

5. Given a doubly linked list with nodes containing integer values, how would you modify the reversal function to also count how many nodes were reversed during the process?

hard

A. Add a counter but increment it only after the loop finishes.

B. Count nodes before reversal and return the count without changes.

C. Add a counter variable initialized to 0, increment it inside the reversal loop, and return it along with the new head.

D. Use recursion to reverse and count nodes simultaneously.

Solution

1. Step 1: Initialize a counter before the loop

   Start a counter at zero to track how many nodes are processed during reversal.

2. Step 2: Increment counter inside the reversal loop

   Each time a node is processed (pointers swapped), increase the counter by one.

3. Step 3: Return both new head and count

   Modify the function to return the new head and the count of reversed nodes.

4. Final Answer:

   Add a counter variable initialized to 0, increment it inside the reversal loop, and return it along with the new head. -> Option C

5. Quick Check:

   Count nodes during reversal loop [OK]

Hint: Count nodes inside reversal loop for accurate total [OK]

Common Mistakes:

• Counting nodes before reversal only
• Incrementing counter after loop ends
• Not returning the count with the head