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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of reversing a doubly linked list

What is the printed state of the doubly linked list after reversing it using the given code?

DSA Python

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

def reverse(head):
    current = head
    temp = None
    while current:
        temp = current.prev
        current.prev = current.next
        current.next = temp
        current = current.prev
    if temp:
        head = temp.prev
    return head

# Create doubly linked list: 1 <-> 2 <-> 3 <-> 4
head = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
head.next = node2
node2.prev = head
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3

# Reverse the list
head = reverse(head)

# Print list forward
result = []
current = head
while current:
    result.append(current.data)
    current = current.next
print(result)

A [4, 3, 2, 1]

B [1, 2, 3, 4]

C [4, 2, 3, 1]

D [1, 3, 2, 4]

💡 Hint

Think about how the prev and next pointers are swapped for each node.

The reverse function swaps the prev and next pointers for each node, effectively reversing the list. After the loop, the head is updated to the last node processed, which becomes the new head. The printed list shows the nodes in reverse order.

🧠 Conceptual

intermediate

Understanding pointer changes in reversing a doubly linked list

When reversing a doubly linked list, which pointers are swapped for each node?

A Swap the data values of adjacent nodes

B Swap only the prev pointers of each node

C Swap only the next pointers of each node

D Swap the next and prev pointers of each node

💡 Hint

Think about what makes the list reverse direction.

Reversing a doubly linked list requires swapping both the next and prev pointers of each node to reverse the direction of traversal.

🔧 Debug

advanced

Identify the error in this reverse function for doubly linked list

What error will this code produce when reversing a doubly linked list?

DSA Python

def reverse(head):
    current = head
    while current:
        temp = current.next
        current.prev, current.next = current.next, current.prev
        current = temp
    return head

A SyntaxError due to invalid tuple assignment

B The function returns the original head, not the new head after reversal

C Infinite loop because current never becomes None

D TypeError because prev and next are not swappable

💡 Hint

Check what happens to the head pointer after swapping pointers.

The code swaps pointers but does not update the head to the new start of the reversed list, so it returns the old head, which is now the tail.

❓ Predict Output

advanced

Output after reversing a doubly linked list with one node

What is the output after reversing a doubly linked list with a single node containing data 10?

DSA Python

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

def reverse(head):
    current = head
    temp = None
    while current:
        temp = current.prev
        current.prev = current.next
        current.next = temp
        current = current.prev
    if temp:
        head = temp.prev
    return head

head = Node(10)
head = reverse(head)

result = []
current = head
while current:
    result.append(current.data)
    current = current.next
print(result)

A [0]

B []

C [10]

D [None]

💡 Hint

Consider how reversing a single node list affects pointers.

A single node reversed remains the same node with no next or prev nodes, so the output is [10].

🚀 Application

expert

Number of nodes after reversing a doubly linked list

After reversing a doubly linked list with 7 nodes, how many nodes does the reversed list contain?

A 7

B 0

C 1

D 14

💡 Hint

Reversing changes order but not the number of nodes.

Reversing a doubly linked list only changes the direction of links, not the number of nodes.

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