Reverse a Doubly Linked List in DSA Python - Execution Trace

Concept Flow - Reverse a Doubly Linked List

Start at head node

↓

For each node: Swap prev and next pointers

↓

Move to new prev (old next) node

↓

Repeat until current node is None

↓

Update head to last processed node

↓

Done: List reversed

We start at the head and for each node, swap its previous and next pointers. Then move to the next node (which is the old next, now prev). Repeat until all nodes are processed. Finally, update the head to the last node processed.

Execution Sample

DSA Python

def reverse_dll(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

This code reverses a doubly linked list by swapping prev and next pointers of each node and updating the head.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at head	Node 1	None	1 <-> 2 <-> 3 <-> 4 <-> None
2	Swap prev and next of Node 1	Node 1	prev: None -> Node 2, next: Node 2 -> None	1 <- 2 <-> 3 <-> 4 <-> None
3	Move current to old next (now prev)	Node 2	current: Node 1 -> Node 2	1 <- 2 <-> 3 <-> 4 <-> None
4	Swap prev and next of Node 2	Node 2	prev: Node 1 -> Node 3, next: Node 3 -> Node 1	1 <- 2 <- 3 <-> 4 <-> None
5	Move current to old next (now prev)	Node 3	current: Node 2 -> Node 3	1 <- 2 <- 3 <-> 4 <-> None
6	Swap prev and next of Node 3	Node 3	prev: Node 2 -> Node 4, next: Node 4 -> Node 2	1 <- 2 <- 3 <- 4 <-> None
7	Move current to old next (now prev)	Node 4	current: Node 3 -> Node 4	1 <- 2 <- 3 <- 4 <-> None
8	Swap prev and next of Node 4	Node 4	prev: Node 3 -> None, next: None -> Node 3	1 <- 2 <- 3 <- 4
9	Move current to old next (now prev)	None	current: Node 4 -> None	1 <- 2 <- 3 <- 4
10	Update head to last processed node	None	head: Node 1 -> Node 4	4 <-> 3 <-> 2 <-> 1 <-> None
11	Return new head	Node 4	None	4 <-> 3 <-> 2 <-> 1 <-> None

💡 current becomes None, all nodes processed, head updated to last node

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
current	Node 1	Node 2	Node 3	Node 4	None	None
temp	None	Node 1.prev (None)	Node 2.prev (Node 1)	Node 3.prev (Node 2)	Node 4.prev (Node 3)	Node 4.prev (Node 3)
head	Node 1	Node 1	Node 1	Node 1	Node 1	Node 4

Key Moments - 3 Insights

Why do we swap prev and next pointers for each node?

Swapping prev and next reverses the direction of links. See execution_table steps 2,4,6,8 where pointers change to reverse the list.

Why do we move current to current.prev after swapping?

After swapping, current.prev points to the original next node. Moving current to current.prev moves forward in the original list. See execution_table steps 3,5,7,9.

How do we update the head after reversal?

After the loop, temp holds the original prev of the last processed node. Due to prior swaps, temp.prev now points to the new head (original tail node). See execution_table step 10.

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'current' node at step 6?

A Node 3

B Node 2

C Node 4

D None

💡 Hint

Check the 'Current Node' column at step 6 in execution_table.

At which step does the 'current' pointer become None?

A Step 8

B Step 10

C Step 9

D Step 11

💡 Hint

Look for 'current' value changing to None in variable_tracker and execution_table.

If we forget to update the head after reversal, what will be the visual state at the end?

A List remains reversed with head at Node 4

B List remains reversed but head points to Node 1 (old head)

C List is not reversed

D List becomes empty

💡 Hint

Refer to execution_table step 10 where head is updated to new node.

Concept Snapshot

Reverse a Doubly Linked List:
- Start at head node
- For each node, swap prev and next pointers
- Move current to old next (now prev)
- Repeat until current is None
- Update head to last processed node
- Return new head

Full Transcript

To reverse a doubly linked list, we start at the head node. For each node, we swap its prev and next pointers to reverse the direction of links. Then we move the current pointer to the old next node, which after swapping is current.prev. We repeat this until current becomes None, meaning we processed all nodes. Finally, we update the head pointer to the last node processed, which is stored in temp.prev. This completes the reversal. The execution table shows each step with pointer changes and the visual state of the list. The variable tracker shows how current, temp, and head change over time. Key moments clarify why we swap pointers, why we move current to current.prev, and how we update the head. The visual quiz tests understanding of these steps. This method reverses the list in place without creating new 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