Reverse a Doubly Linked List in DSA Go - Execution Trace

Concept Flow - Reverse a Doubly Linked List

Start at head node

↓

For each node: Swap prev and next pointers

↓

Move to original next node (now prev after swap)

↓

Repeat until current node is null

↓

Set 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 original next but now prev). Repeat until all nodes are processed. Finally, update the head to the last node processed.

Execution Sample

DSA Go

func reverseDoublyLinkedList(head *Node) *Node {
    current := head
    var temp *Node
    for current != nil {
        temp = current.prev
        current.prev = current.next
        current.next = temp
        current = current.prev
    }
    if temp != nil {
        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 pointer at the end.

Execution Table

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

💡 Current node becomes null after processing all nodes, loop ends and head is updated.

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	null	null
temp	nil	null	Node 1	Node 2	Node 3	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, and 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 to current.prev continues traversal forward in the original list. See steps 3, 5, 7, and 9.

How do we update the head after reversal?

The last processed node before current becomes null is stored in temp. The new head is temp.prev after the final swap. See step 10 where head changes from Node 1 to Node 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what are the prev and next pointers of Node 2 after swapping?

A prev: Node 3, next: Node 1

B prev: Node 1, next: Node 3

C prev: Node 3, next: Node 4

D prev: Node 1, next: Node 4

💡 Hint

Check the 'Pointer Changes' column at step 4 in the execution_table.

At which step does the current pointer become null, ending the loop?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look at the 'Current Node' column and see when it becomes null.

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

A List remains reversed with head at Node 4

B List remains reversed but head still points to Node 1

C List is not reversed

D List is empty

💡 Hint

Refer to the 'head' variable changes in variable_tracker and step 10 in execution_table.

Concept Snapshot

Reverse a Doubly Linked List:
- Traverse from head to end
- For each node, swap prev and next pointers
- Move to original next node (now prev)
- After traversal, update head to last processed node
- Result: list direction reversed, head updated

Full Transcript

To reverse a doubly linked list, start at the head node. For each node, swap its prev and next pointers to reverse the direction of links. Then move to the original next node, which after swapping is accessible via current.prev. Continue this until the current node becomes null, meaning the end of the list is reached. Finally, update the head pointer to the last node processed before current became null. This process reverses the list in place without creating new nodes. The execution table shows each step with pointer changes and the visual state of the list. The variable tracker follows current, temp, and head pointers through the process. Key moments clarify why pointers are swapped and how traversal continues. The visual quiz tests understanding of pointer changes and loop termination.

Practice

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

easy

A. To sort the list in ascending order

B. To delete all nodes from the list

C. To make the last node the first and the first node the last

D. To add a new node at the end

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.

2. Step 2: Define reversing operation

   Reversing means swapping the previous and next pointers for all nodes, so the last node becomes the first.

3. Final Answer:

   To make the last node the first and the first node the last -> Option C

4. Quick Check:

   Reverse = swap previous and next pointers [OK]

Hint: Reversing swaps next and previous pointers [OK]

Common Mistakes:

• Confusing reversing with sorting
• Thinking reversing deletes nodes
• Assuming reversing adds nodes

2. Which of the following Go 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, 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 multiple assignment in Go

   Go allows swapping two variables in one line using multiple assignment.

2. Step 2: Identify correct swap syntax

   The correct way to swap is curr.next, curr.prev = curr.prev, curr.next which exchanges the values.

3. Final Answer:

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

4. Quick Check:

   Swap pointers with multiple assignment [OK]

Hint: Use Go's multiple assignment to swap pointers [OK]

Common Mistakes:

• Assigning one pointer twice without swapping
• Using separate lines causing overwrite
• Not swapping pointers at all

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

type Node struct {
    data int
    prev *Node
    next *Node
}

func reverse(head *Node) *Node {
    var temp *Node
    curr := head
    for curr != nil {
        temp = curr.prev
        curr.prev = curr.next
        curr.next = temp
        curr = curr.prev
    }
    if temp != nil {
        head = temp.prev
    }
    return head
}

// List before reversal: 1 <-> 2 <-> 3 <-> nil
// After reversal, print from new head
func printList(head *Node) {
    curr := head
    for curr != nil {
        fmt.Print(curr.data, " <-> ")
        curr = curr.next
    }
    fmt.Println("nil")
}

medium

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

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

C. nil

D. 1 <-> nil

Solution

1. Step 1: Trace pointer swaps in the loop

   Each node swaps its prev and next pointers, moving curr to original next node via curr.prev after swap.

2. Step 2: Update head to last processed node

   After loop, head is set to temp.prev which points to the new first node (original last node).

3. Final Answer:

   3 <-> 2 <-> 1 <-> nil -> Option B

4. Quick Check:

   Reversed list prints nodes in reverse order [OK]

Hint: Reversed list prints nodes backward [OK]

Common Mistakes:

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

4. Identify the bug in this Go function that attempts to reverse a doubly linked list:

func reverse(head *Node) *Node {
    curr := head
    for curr != nil {
        curr.prev, curr.next = curr.next, curr.prev
        curr = curr.next
    }
    return head
}

medium

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

B. The pointers are not swapped correctly

C. The function does not return the new head

D. The function deletes nodes accidentally

Solution

1. Step 1: Analyze pointer swapping and traversal

   The pointers are swapped correctly, but after swapping, curr.next points to the previous node, so moving curr to curr.next moves backward.

2. Step 2: Identify correct traversal direction

   After swapping, curr should move to curr.prev (original next) to continue forward traversal.

3. Final Answer:

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

4. Quick Check:

   Traverse using curr.prev after swap [OK]

Hint: After swap, move curr to curr.prev, not curr.next [OK]

Common Mistakes:

• Moving curr in wrong direction after swap
• Not updating head to new first node
• Swapping pointers incorrectly

5. You have a doubly linked list with nodes containing integers. After reversing it using the standard pointer swap method, you want to find the sum of all nodes at even positions (2nd, 4th, etc.) in the reversed list. Which approach correctly combines reversal and summation?

hard

A. Sum all nodes without reversal

B. Sum nodes at even positions before reversal, then reverse the list

C. Reverse the list and sum nodes at odd positions instead

D. First reverse the list, then traverse from new head summing nodes at even positions

Solution

1. Step 1: Reverse the doubly linked list

   Use pointer swapping to reverse the list so the order is changed.

2. Step 2: Traverse from new head and sum nodes at even positions

   After reversal, positions change, so summing even positions requires traversal from new head counting nodes.

3. Final Answer:

   First reverse the list, then traverse from new head summing nodes at even positions -> Option D

4. Quick Check:

   Reverse first, then sum even positions [OK]

Hint: Reverse first, then sum nodes by position [OK]

Common Mistakes:

• Summing before reversal causing wrong positions
• Summing odd positions instead of even
• Ignoring reversal effect on node order