Reverse a Singly Linked List Iterative in DSA Python - Build from Scratch

Reverse a Singly Linked List Iterative

📖 Scenario: You are working on a simple program that manages a list of tasks. Each task is stored as a node in a singly linked list. Sometimes, you want to reverse the order of tasks to see them from last to first.

🎯 Goal: Build a program that creates a singly linked list with specific tasks, then reverses the list using an iterative method, and finally prints the reversed list.

📋 What You'll Learn

Create a singly linked list with nodes containing the exact values: 'Task1', 'Task2', 'Task3', 'Task4'

Use variables named head, prev, current, and next_node as needed

Implement the iterative reversal of the singly linked list

Print the reversed linked list in the format: Task4 -> Task3 -> Task2 -> Task1 -> None

💡 Why This Matters

🌍 Real World

Reversing linked lists is useful in many applications like undo operations, navigation history, and data processing pipelines where order reversal is needed.

💼 Career

Understanding linked list reversal is a common interview question and helps build foundational skills for working with dynamic data structures in software development.

1

Create the singly linked list nodes

Define a class called Node with an __init__ method that takes data and sets self.data and self.next. Then create four nodes with data 'Task1', 'Task2', 'Task3', and 'Task4'. Link them so that head points to the first node.

DSA Python

# Define Node class and create linked list nodes
# Your code here

Hint

Start by defining the Node class with data and next attributes. Then create four nodes and link them by setting the next attribute of each node to the next node.

2

Set up variables for iterative reversal

Create two variables: prev and current. Set prev to None and current to head.

DSA Python

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

head = Node('Task1')
second = Node('Task2')
third = Node('Task3')
fourth = Node('Task4')

head.next = second
second.next = third
third.next = fourth

# Create variables prev and current for reversal
# Your code here

Hint

Set prev to None because before reversal there is no previous node. Set current to head to start from the first node.

3

Iteratively reverse the linked list

Use a while loop that runs while current is not None. Inside the loop, create a variable next_node to store current.next. Then set current.next to prev. Move prev to current and current to next_node. After the loop, set head to prev.

DSA Python

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

head = Node('Task1')
second = Node('Task2')
third = Node('Task3')
fourth = Node('Task4')

head.next = second
second.next = third
third.next = fourth

prev = None
current = head

# Reverse the linked list iteratively
# Your code here

Hint

Inside the loop, save the next node, reverse the link, then move prev and current forward. After the loop, prev will be the new head.

4

Print the reversed linked list

Create a variable temp and set it to head. Use a while loop that runs while temp is not None. Inside the loop, print temp.data followed by ' -> ' without a newline. Move temp to temp.next. After the loop, print 'None'.

DSA Python

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

head = Node('Task1')
second = Node('Task2')
third = Node('Task3')
fourth = Node('Task4')

head.next = second
second.next = third
third.next = fourth

prev = None
current = head

while current is not None:
    next_node = current.next
    current.next = prev
    prev = current
    current = next_node

head = prev

# Print the reversed linked list
# Your code here

Hint

Use a temporary pointer to go through the reversed list and print each node's data followed by an arrow. End with 'None'.

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