Reverse a Singly Linked List Iterative in DSA Go

Mental Model

We change the direction of each link one by one so the list points backward instead of forward.

Analogy: Imagine walking down a path and turning around at each step to face where you came from, so you end up walking back the way you came.

head -> 1 -> 2 -> 3 -> null
prev=null ↑ curr=1

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null

Goal: Reverse the list so it becomes 3 -> 2 -> 1 -> null

Step 1: Save next node after current (2), reverse current's pointer to prev (null), move prev to current (1), move current to next (2)

1 -> null
prev=1 ↑ curr=2 -> 3 -> null

Why: We start reversing the first node's pointer to point backward (null) and move forward

Step 2: Save next node after current (3), reverse current's pointer to prev (1), move prev to current (2), move current to next (3)

2 -> 1 -> null
prev=2 ↑ curr=3 -> null

Why: Reverse second node's pointer to point back to first node

Step 3: Save next node after current (null), reverse current's pointer to prev (2), move prev to current (3), move current to next (null)

3 -> 2 -> 1 -> null
prev=3 ↑ curr=null

Why: Reverse last node's pointer to point back to second node, current is now null so stop

Result:

3 -> 2 -> 1 -> null

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
    val  int
    next *Node
}

func reverseList(head *Node) *Node {
    var prev *Node = nil
    curr := head
    for curr != nil {
        nextTemp := curr.next // save next node
        curr.next = prev     // reverse pointer
        prev = curr          // move prev forward
        curr = nextTemp      // move curr forward
    }
    return prev
}

func printList(head *Node) {
    curr := head
    for curr != nil {
        fmt.Printf("%d", curr.val)
        if curr.next != nil {
            fmt.Printf(" -> ")
        }
        curr = curr.next
    }
    fmt.Println(" -> null")
}

func main() {
    // Create list 1 -> 2 -> 3 -> null
    n3 := &Node{val: 3, next: nil}
    n2 := &Node{val: 2, next: n3}
    n1 := &Node{val: 1, next: n2}

    fmt.Print("Original list: ")
    printList(n1)

    reversed := reverseList(n1)

    fmt.Print("Reversed list: ")
    printList(reversed)
}

for curr != nil {

loop until we reach the end of the list

nextTemp := curr.next // save next node

keep next node safe before changing pointer

curr.next = prev // reverse pointer

reverse current node's pointer to previous node

prev = curr // move prev forward

advance prev to current node

curr = nextTemp // move curr forward

advance curr to next node saved earlier

return prev

prev is 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 reverse pointers

Space: O(1) because we only use a few extra variables, no extra list

vs Alternative: Compared to recursive reversal which uses O(n) space on call stack, iterative is more space efficient

Edge Cases

empty list (head is nil)

function returns nil immediately, no reversal needed

DSA Go

for curr != nil {

single node list

pointer reversal sets next to nil but list remains same

DSA Go

curr.next = prev     // reverse pointer

When to Use This Pattern

When you need to reverse the order of a singly linked list, use the iterative reversal pattern to change pointers one by one efficiently.

Common Mistakes

Mistake: Not saving the next node before reversing pointer causes loss of access to rest of list
Fix: Always save curr.next in a temporary variable before changing curr.next

Mistake: Returning the original head instead of the new head after reversal
Fix: Return prev pointer after loop ends as it points to new head

Summary

Reverses a singly linked list by changing each node's pointer to the previous node.

Use when you want to reverse the order of elements in a singly linked list efficiently.

The key is to save the next node before reversing the pointer to avoid losing the rest of the list.

Practice

1. What is the main purpose of the iterative method to reverse a singly linked list?

easy

A. To sort the linked list in ascending order

B. To create a new linked list with reversed elements

C. To delete all nodes and recreate them in reverse order

D. To change the direction of the links between nodes one by one

Solution

1. Step 1: Understand the linked list structure

   A singly linked list has nodes pointing to the next node only, so reversing means changing these pointers.

2. Step 2: Purpose of iterative reversal

   The iterative method changes the next pointer of each node to point to the previous node, reversing the list in place.

3. Final Answer:

   To change the direction of the links between nodes one by one -> Option D

4. Quick Check:

   Reversing means changing links direction [OK]

Hint: Reversing means flipping links, not creating new nodes [OK]

Common Mistakes:

• Thinking it creates a new list instead of reversing in place
• Confusing reversal with sorting
• Assuming nodes are deleted and recreated

2. Which of the following Go code snippets correctly initializes pointers for iterative reversal of a singly linked list?

easy

A. var prev = head; current := nil

B. var prev *Node = nil; current := head

C. prev := head; current := head.next

D. var prev *Node = head; current := head

Solution

1. Step 1: Initialization for reversal

   We start with prev as nil because the new tail will point to nil, and current at head to traverse the list.

2. Step 2: Check each option

   var prev *Node = nil; current := head correctly sets prev to nil and current to head. Others incorrectly assign prev or current.

3. Final Answer:

   var prev *Node = nil; current := head -> Option B

4. Quick Check:

   Prev starts nil, current at head [OK]

Hint: Prev starts nil, current starts at head [OK]

Common Mistakes:

• Setting prev to head initially
• Setting current to nil at start
• Mixing pointer assignments

3. What will be the output linked list after running this Go code to reverse a singly linked list?

type Node struct {
    Val  int
    Next *Node
}

func reverseList(head *Node) *Node {
    var prev *Node = nil
    current := head
    for current != nil {
        nextTemp := current.Next
        current.Next = prev
        prev = current
        current = nextTemp
    }
    return prev
}

// Input list: 1 -> 2 -> 3 -> nil
// Call: reverseList(head)

medium

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

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

C. nil -> 3 -> 2 -> 1

D. 3 -> 1 -> 2 -> nil

Solution

1. Step 1: Trace the reversal loop

   Initially prev=nil, current=1. Each iteration reverses current.Next to prev and moves pointers forward.

2. Step 2: Final reversed list

   After loop, prev points to node with Val=3, linked as 3->2->1->nil.

3. Final Answer:

   3 -> 2 -> 1 -> nil -> Option A

4. Quick Check:

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

Hint: Follow pointer changes step-by-step [OK]

Common Mistakes:

• Confusing original and reversed order
• Misunderstanding pointer updates
• Assuming list remains unchanged

4. Identify the error in this Go code snippet for reversing a singly linked list iteratively:

func reverseList(head *Node) *Node {
    var prev *Node = head
    current := head
    for current != nil {
        nextTemp := current.Next
        current.Next = prev
        prev = current
        current = nextTemp
    }
    return prev
}

medium

A. prev should be initialized to nil, not head

B. current should be initialized to nil

C. nextTemp should be initialized outside the loop

D. The function should return current, not prev

Solution

1. Step 1: Check initialization of prev

   Prev must start as nil because the new tail's next is nil. Setting prev=head causes a cycle.

2. Step 2: Effect of wrong prev initialization

   Setting prev=head makes current.Next point to itself on first iteration, causing infinite loop or wrong reversal.

3. Final Answer:

   prev should be initialized to nil, not head -> Option A

4. Quick Check:

   Prev starts nil to avoid cycles [OK]

Hint: Prev must start nil to break old links [OK]

Common Mistakes:

• Initializing prev to head causing cycles
• Returning current instead of prev
• Misplacing nextTemp initialization

5. Given a singly linked list with nodes containing values 10 -> 20 -> 30 -> 40 -> nil, write the final linked list after applying iterative reversal twice in a row.

hard

A. 40 -> 30 -> 20 -> 10 -> nil

B. nil

C. 10 -> 20 -> 30 -> 40 -> nil

D. 40 -> 10 -> 20 -> 30 -> nil

Solution

1. Step 1: First reversal

   Reversing 10->20->30->40->nil gives 40->30->20->10->nil.

2. Step 2: Second reversal

   Reversing again restores original order: 10->20->30->40->nil.

3. Final Answer:

   10 -> 20 -> 30 -> 40 -> nil -> Option C

4. Quick Check:

   Double reversal returns original list [OK]

Hint: Reversing twice returns original list [OK]

Common Mistakes:

• Assuming second reversal changes order differently
• Confusing node values after reversal
• Thinking list becomes empty