Reverse a Singly Linked List Iterative in DSA Python

Mental Model

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

Analogy: Imagine a line of people holding hands forward. We ask each person to turn around and hold the hand of the person behind them instead.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

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

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

Step 1: Initialize prev to null and curr to head (node 1)

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

Why: We start with prev as null because the new tail will point to null

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

1 -> null [prev]
2 -> 3 -> null [curr]

Why: We reverse the first link and move forward to continue reversing

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

2 -> 1 -> null [prev]
3 -> null [curr]

Why: We reverse the second link and move forward

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

3 -> 2 -> 1 -> null [prev]
curr = null

Why: We reverse the last link; curr is now null so we stop

Result:

3 -> 2 -> 1 -> null

Annotated Code

DSA Python

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

def reverse_linked_list(head):
    prev = None
    curr = head
    while curr is not None:
        next_node = curr.next  # save next node
        curr.next = prev       # reverse pointer
        prev = curr            # move prev forward
        curr = next_node       # move curr forward
    return prev

def print_list(head):
    curr = head
    result = []
    while curr:
        result.append(str(curr.val))
        curr = curr.next
    print(' -> '.join(result) + ' -> null')

# Driver code
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

print_list(head)
reversed_head = reverse_linked_list(head)
print_list(reversed_head)

while curr is not None:

loop until we reach the end of the list

next_node = curr.next # save next node

keep track of next node 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 = next_node # move curr forward

advance curr to next node to continue

return prev

prev is new head after full reversal

Output

1 -> 2 -> 3 -> null

3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) because we visit each node once to reverse its pointer

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 uses constant space

Edge Cases

empty list (head is null)

function returns null immediately, no reversal needed

DSA Python

while curr is not None:

single node list

pointer reversal does nothing visible, returns same single node

DSA Python

while curr is not None:

When to Use This Pattern

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

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 variable before changing curr.next

Mistake: Returning head instead of prev after reversal
Fix: Return prev because it points to new head after reversal

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 nodes 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 reversing a singly linked list iteratively?

easy

A. To remove duplicate nodes from the list

B. To sort the list in ascending order

C. To change the direction of all links so the list order is reversed

D. To find the middle node of the list

Solution

1. Step 1: Understand the linked list structure

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

2. Step 2: Purpose of iterative reversal

   The iterative method changes each node's next pointer to the previous node, effectively reversing the list order.

3. Final Answer:

   To change the direction of all links so the list order is reversed -> Option C

4. Quick Check:

   Reversing means flipping links direction [OK]

Hint: Reversing flips all next pointers to previous nodes [OK]

Common Mistakes:

• Confusing reversal with sorting
• Thinking reversal deletes nodes
• Assuming reversal finds middle node

2. Which of the following is the correct way to initialize pointers for iterative reversal of a singly linked list in Python?

easy

A. prev = head; current = head.next

B. prev = null; current = head

C. prev = head; current = null

D. prev = null; current = null

Solution

1. Step 1: Understand pointer roles

   Prev starts as null because the new tail will point to null; current starts at head to traverse the list.

2. Step 2: Correct initialization

   Setting prev = null and current = head allows iteration from the start with no previous node initially.

3. Final Answer:

   prev = null; current = head -> Option B

4. Quick Check:

   Prev null, current at head to start [OK]

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

Common Mistakes:

• Setting prev to head initially
• Starting current as null
• Both pointers as null

3. What will be the output linked list after running the iterative reversal code on this list: 1 -> 2 -> 3 -> null?

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. null -> 3 -> 2 -> 1

D. 2 -> 3 -> 1 -> null

Solution

1. Step 1: Trace reversal process

   Initially: prev=null, current=1. After first iteration, 1 points to null. Then 2 points to 1, then 3 points to 2.

2. Step 2: Final reversed list

   The list becomes 3 -> 2 -> 1 -> null after all nodes reverse their next pointers.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option A

4. Quick Check:

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

Hint: Last node becomes new head after reversal [OK]

Common Mistakes:

• Not updating pointers correctly
• Confusing original and reversed order
• Including null as a node

4. Identify the error in this iterative reversal code snippet:

def reverse(head):
    prev = head
    current = null
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

medium

A. prev should start as null, current as head

B. The loop condition should be 'while prev' instead of 'while current'

C. current.next assignment is reversed, should be 'prev.next = current'

D. Function should return current instead of prev

Solution

1. Step 1: Check pointer initialization

   Prev should be null initially because the new tail points to null; current should start at head to traverse.

2. Step 2: Loop condition and pointer updates

   Loop runs while current is not null; current.next is set to prev correctly; returning prev gives new head.

3. Final Answer:

   prev should start as null, current as head -> Option A

4. Quick Check:

   Prev null, current head to start loop [OK]

Hint: Prev null, current head to avoid skipping nodes [OK]

Common Mistakes:

• Starting prev at head causes cycle
• Loop condition incorrect
• Returning wrong pointer

5. Given a singly linked list with nodes containing values [10, 20, 30, 40, 50], which iterative reversal step correctly updates the pointers after processing the first two nodes?

hard

A. After first node: 10 -> 20; After second node: 20 -> null

B. After first node: 10 -> 20 -> null; After second node: 20 -> 10 -> null

C. After first node: null -> 10; After second node: 10 -> 20

D. After first node: 10 -> null; After second node: 20 -> 10 -> null

Solution

1. Step 1: Reverse first node pointer

   Initially, prev=null, current=10. After first iteration, 10.next = null, so list is 10 -> null.

2. Step 2: Reverse second node pointer

   Next, current=20. Set 20.next = prev (which is 10), so list is 20 -> 10 -> null.

3. Final Answer:

   After first node: 10 -> null; After second node: 20 -> 10 -> null -> Option D

4. Quick Check:

   Each node points back to previous [OK]

Hint: Each step points current node to previous node [OK]

Common Mistakes:

• Not setting first node's next to null
• Linking nodes forward instead of backward
• Confusing order of pointer updates