Reverse a Doubly Linked List in DSA Python

Mental Model

To reverse a doubly linked list, we swap the next and previous links for each node and move forward until all nodes are reversed.

Analogy: Imagine walking backward on a path where each step has a forward and backward arrow; reversing means swapping these arrows so you can walk the path in the opposite direction.

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

Dry Run Walkthrough

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

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

Step 1: swap next and prev of node 1, move curr to prev (which was originally next)

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

Why: Swapping pointers reverses direction; moving curr to prev continues traversal forward in original list

Step 2: swap next and prev of node 2, move curr to prev

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

Why: Continue swapping pointers to reverse links for each node

Step 3: swap next and prev of node 3, move curr to prev

null ← 1 ← 2 ← 3 null
↑curr at null (end)

Why: Last node reversed; curr is now null, stop traversal

Step 4: update head to last processed node (3)

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

Why: New head is the last node processed after reversal

Result:

null ← 3 ↔ 2 ↔ 1 -> null

Annotated Code

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node
        new_node.prev = curr

    def reverse(self):
        curr = self.head
        temp = None
        while curr:
            temp = curr.prev  # store prev
            curr.prev = curr.next  # swap prev and next
            curr.next = temp
            curr = curr.prev  # move to next node in original list
        if temp:
            self.head = temp.prev  # update head to last node processed

    def __str__(self):
        result = []
        curr = self.head
        while curr:
            result.append(str(curr.data))
            curr = curr.next
        return ' ↔ '.join(result) + ' -> null'

# Driver code
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
print("Original list:", dll)
dll.reverse()
print("Reversed list:", dll)

while curr:

iterate through each node until end

temp = curr.prev # store prev

keep original prev to use after swapping

curr.prev = curr.next # swap prev and next

reverse the direction of prev pointer

curr.next = temp

reverse the direction of next pointer

curr = curr.prev # move to next node in original list

advance to next node using swapped pointers

if temp:

check if list was not empty to update head

self.head = temp.prev # update head to last node processed

set new head after reversal

Output

Original list: 1 ↔ 2 ↔ 3 -> null

Reversed list: 3 ↔ 2 ↔ 1 -> null

Complexity Analysis

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

Space: O(1) because reversal is done in place without extra storage

vs Alternative: Compared to creating a new reversed list (O(n) time and space), this in-place reversal saves memory

Edge Cases

empty list

reverse does nothing, head remains None

DSA Python

if temp:

single node list

reverse swaps pointers but list remains same, head unchanged

DSA Python

if temp:

When to Use This Pattern

When you need to reverse the order of elements in a doubly linked list, use pointer swapping to reverse links efficiently.

Common Mistakes

Mistake: Advancing curr using curr.next after swapping pointers
Fix: Advance curr using curr.prev because pointers are swapped

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

Summary

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

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

The key insight is to swap pointers and move forward using the swapped links until all nodes are reversed.

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 new head and changing traversal direction.

3. Final Answer:

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

4. Quick Check:

   Reversing swaps pointers to reverse traversal [OK]

Hint: Reversing swaps previous and next pointers [OK]

Common Mistakes:

• Thinking reversing deletes nodes
• Confusing reversing with sorting
• Assuming it converts to singly linked list

2. Which of the following is the correct way to swap the next and prev pointers of a node curr in Python?

easy

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

B. curr.next, curr.prev = curr.prev, curr.next

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

D. curr.next = curr.next; curr.prev = curr.prev

Solution

1. Step 1: Understand Python tuple unpacking

   Using a, b = b, a swaps values of a and b simultaneously without temporary variable.

2. Step 2: Apply to pointers

   Swapping curr.next and curr.prev correctly uses curr.next, curr.prev = curr.prev, curr.next.

3. Final Answer:

   curr.next, curr.prev = curr.prev, curr.next -> Option B

4. Quick Check:

   Tuple unpacking swaps pointers correctly [OK]

Hint: Use tuple unpacking to swap pointers in one line [OK]

Common Mistakes:

• Assigning sequentially causing both to be same
• Not swapping both pointers
• Using incorrect order in assignment

3. Given the doubly linked list: 1 <-> 2 <-> 3 <-> null, what will be the list after reversing it using the standard reverse algorithm?

medium

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

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

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

D. 3 -> 2 -> 1 -> null (singly linked list)

Solution

1. Step 1: Original list traversal

   The list is 1 <-> 2 <-> 3 <-> null, head at 1, tail at 3.

2. Step 2: Reverse pointers

   Swapping next and prev pointers reverses the list, making 3 the new head and 1 the new tail.

3. Final Answer:

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

4. Quick Check:

   Reversed list order is 3, 2, 1 [OK]

Hint: Reversed list order is original tail to head [OK]

Common Mistakes:

• Confusing original order with reversed
• Misplacing null pointer
• Assuming singly linked list after reverse

4. What is the error in this code snippet for reversing a doubly linked list?

def reverse(head):
    curr = head
    while curr:
        curr.next = curr.prev
        curr.prev = curr.next
        curr = curr.prev
    return head

medium

A. The code correctly reverses the list

B. The loop condition should be while curr.next

C. Pointers are not swapped simultaneously causing incorrect links

D. The function should return curr instead of head

Solution

1. Step 1: Analyze pointer swapping

   Assigning curr.next = curr.prev then curr.prev = curr.next sequentially overwrites curr.next before using it, losing original value.

2. Step 2: Effect on traversal

   Because pointers are not swapped simultaneously, traversal using curr = curr.prev fails and links become incorrect.

3. Final Answer:

   Pointers are not swapped simultaneously causing incorrect links -> Option C

4. Quick Check:

   Swap pointers simultaneously to avoid overwriting [OK]

Hint: Swap pointers in one line to avoid overwriting [OK]

Common Mistakes:

• Swapping pointers in two separate assignments
• Returning old head instead of new head
• Incorrect loop condition

5. You have a doubly linked list with nodes containing integer values. After reversing it, you want to print the list from the new head to the end. Which of the following code snippets correctly prints the reversed list?

hard

A. curr = reversed_head
while curr:
print(curr.data, end=' <-> ')
curr = curr.prev
print('null')

B. curr = reversed_head
while curr.prev:
print(curr.data, end=' <-> ')
curr = curr.prev
print('null')

C. curr = original_head
while curr:
print(curr.data, end=' <-> ')
curr = curr.next
print('null')

D. curr = reversed_head
while curr:
print(curr.data, end=' <-> ')
curr = curr.next
print('null')

Solution

1. Step 1: Identify traversal direction after reversing

   After reversing, the new head points to the start of the reversed list, and traversal should use next pointers to move forward.

2. Step 2: Correct printing loop

   Starting from reversed_head, printing curr.data and moving with curr = curr.next prints the list in correct order until curr is null.

3. Final Answer:

   curr = reversed_head while curr: print(curr.data, end=' <-> ') curr = curr.next print('null') -> Option D

4. Quick Check:

   Traverse reversed list using next pointers from new head [OK]

Hint: Print using next pointers from new head after reverse [OK]

Common Mistakes:

• Using prev pointer to traverse forward
• Starting from original head after reverse
• Loop condition stopping early