Reverse a Doubly Linked List in DSA Go

Mental Model

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

Analogy: Imagine walking backward on a path where each step has a sign pointing forward and backward; reversing means swapping these signs 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: At node 1, swap prev and next pointers

null ← 1 ← null  2 ↔ 3 -> null
↑curr moves to original next (2)

Why: Swapping pointers reverses direction for current node; move to next node to continue

Step 2: At node 2, swap prev and next pointers

null ← 1 ← null  2 ← 1  3 -> null
↑curr moves to original next (3)

Why: Continue swapping pointers to reverse links for all nodes

Step 3: At node 3, swap prev and next pointers

null ← 1 ← null  2 ← 1  3 ← 2  null
↑curr moves to original next (null), stop

Why: Last node reversed; curr is null so reversal is complete

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

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

Why: Head must point to new first node after reversal

Result:

null ← 3 ↔ 2 ↔ 1 -> null

Annotated Code

DSA Go

package main

import "fmt"

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

type DoublyLinkedList struct {
	head *Node
}

func (dll *DoublyLinkedList) append(val int) {
	newNode := &Node{val: val}
	if dll.head == nil {
		dll.head = newNode
		return
	}
	curr := dll.head
	for curr.next != nil {
		curr = curr.next
	}
	curr.next = newNode
	newNode.prev = curr
}

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

func (dll *DoublyLinkedList) printList() {
	curr := dll.head
	for curr != nil {
		fmt.Printf("%d", curr.val)
		if curr.next != nil {
			fmt.Printf(" ↔ ")
		}
		curr = curr.next
	}
	fmt.Println()
}

func main() {
	dll := &DoublyLinkedList{}
	dll.append(1)
	dll.append(2)
	dll.append(3)
	fmt.Print("Original list: ")
	dll.printList()
	dll.reverse()
	fmt.Print("Reversed list: ")
	dll.printList()
}

for curr != nil {

iterate through each node until end

temp = curr.prev

store current node's prev pointer temporarily

curr.prev = curr.next

swap prev and next pointers to reverse direction

curr.next = temp

complete swapping pointers for current node

curr = curr.prev

move curr forward using new prev pointer (original next)

if temp != nil { dll.head = temp.prev }

update head to new first node after reversal

Output

Original list: 1 ↔ 2 ↔ 3

Reversed list: 3 ↔ 2 ↔ 1

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 and head remains nil

DSA Go

for curr != nil {

single node list

pointers swap but list remains same; head stays at single node

DSA Go

for curr != nil {

When to Use This Pattern

When you see a problem asking to reverse a doubly linked list, reach for pointer swapping because each node has two links that must be swapped to reverse direction.

Common Mistakes

Mistake: Moving curr to curr.next instead of curr.prev after swapping pointers
Fix: After swapping, move curr to curr.prev because prev now points to the original next node

Mistake: Not updating the head pointer after reversal
Fix: Update head to the last processed node's prev pointer after 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 at each node reverses the list direction.

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