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

Reverse a Singly Linked List Iterative

📖 Scenario: Imagine you have a chain of train cars connected one after another. Sometimes, you want to reverse the order of the cars so the last car becomes the first and the first becomes the last.In programming, a singly linked list is like that chain, where each car (node) points to the next one. Your task is to reverse this chain using a simple step-by-step method.

🎯 Goal: You will build a program that creates a singly linked list with exact values, then reverses it using an iterative method, and finally prints the reversed list.

📋 What You'll Learn

Create a singly linked list with nodes containing values 1, 2, 3, 4, 5 in that order

Use three pointers named prev, current, and next to reverse the list iteratively

Print the reversed linked list in the format: 5 -> 4 -> 3 -> 2 -> 1 -> null

💡 Why This Matters

🌍 Real World

Reversing linked lists is useful in many software tasks like undo operations, navigation history, and data reordering.

💼 Career

Understanding linked list reversal is a common interview question and helps build strong problem-solving skills in data structures.

1

Create the singly linked list

Define a struct called Node with an int data and a Node* next. Then create five nodes with values 1, 2, 3, 4, 5 linked in order, and set a pointer head to the first node.

DSA C++

// Define Node struct and create linked list nodes with values 1 to 5
// Link nodes in order and set head to first node
// Your code here

Hint

Think of each node as a train car holding a number. Connect each car to the next by setting the next pointer.

2

Set up pointers for reversal

Create three pointers: prev set to nullptr, current set to head, and next set to nullptr. These will help you reverse the list step by step.

DSA C++

struct Node {
    int data;
    Node* next;
};

Node node1 = {1, nullptr};
Node node2 = {2, nullptr};
Node node3 = {3, nullptr};
Node node4 = {4, nullptr};
Node node5 = {5, nullptr};

node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = &node5;

Node* head = &node1;

// Create pointers prev, current, and next for reversal
// Your code here

Hint

These pointers will help you keep track of nodes as you reverse the links one by one.

3

Reverse the linked list iteratively

Use a while loop that runs while current is not nullptr. Inside the loop, set next to current->next, then change current->next to prev. Move prev to current, and current to next. After the loop, set head to prev.

DSA C++

struct Node {
    int data;
    Node* next;
};

Node node1 = {1, nullptr};
Node node2 = {2, nullptr};
Node node3 = {3, nullptr};
Node node4 = {4, nullptr};
Node node5 = {5, nullptr};

node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = &node5;

Node* head = &node1;

Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;

// Reverse the linked list using a while loop
// Your code here

Hint

Think of changing the direction of each link one by one until the whole chain is reversed.

4

Print the reversed linked list

Use a Node* pointer named temp set to head. Use a while loop to print each node's data followed by " -> ". Move temp to temp->next each time. After the loop, print "null".

DSA C++

struct Node {
    int data;
    Node* next;
};

Node node1 = {1, nullptr};
Node node2 = {2, nullptr};
Node node3 = {3, nullptr};
Node node4 = {4, nullptr};
Node node5 = {5, nullptr};

node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = &node5;

Node* head = &node1;

Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;

while (current != nullptr) {
    next = current->next;
    current->next = prev;
    prev = current;
    current = next;
}
head = prev;

// Print the reversed linked list
// Your code here

Hint

Print each node's value followed by an arrow until you reach the end, then print "null".

Practice

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

easy

A. To sort the nodes in ascending order

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

C. To delete all nodes from the list

D. To create a new linked list with the same elements

Solution

1. Step 1: Understand the linked list structure

   A singly linked list has nodes connected by pointers going one way only.

2. Step 2: Purpose of iterative reversal

   The iterative method changes each node's pointer to point backward, reversing the list.

3. Final Answer:

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

4. Quick Check:

   Reversing = Changing links direction [OK]

Hint: Think of flipping arrows between nodes one at a time [OK]

Common Mistakes:

• Confusing reversal with deletion
• Thinking it sorts the list
• Assuming it creates a new list

2. Which of the following is the correct syntax to initialize the previous pointer to NULL in C++ before starting the reversal?

easy

A. Node* prev = NULL;

B. Node prev = NULL;

C. Node prev* = 0;

D. Node prev = 0;

Solution

1. Step 1: Understand pointer initialization

   In C++, pointers are declared with * and can be set to NULL or nullptr.

2. Step 2: Correct pointer declaration

   "Node* prev = NULL;" correctly declares a pointer named prev and initializes it to NULL.

3. Final Answer:

   Node* prev = NULL; -> Option A

4. Quick Check:

   Pointer prev initialized to NULL [OK]

Hint: Use * for pointers and assign NULL or nullptr [OK]

Common Mistakes:

• Declaring pointer without *
• Assigning NULL to non-pointer variable
• Using 0 without pointer declaration

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

medium

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

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

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

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

Solution

1. Step 1: Trace reversal of 1 -> 2 -> 3

   Start with prev = NULL, curr = 1. Change 1's next to NULL, move prev to 1, curr to 2.

2. Step 2: Continue reversing links

   Change 2's next to 1, move prev to 2, curr to 3. Then change 3's next to 2, prev to 3, curr to NULL.

3. Final Answer:

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

4. Quick Check:

   Reversed list = 3 -> 2 -> 1 [OK]

Hint: Reverse pointers one by one from head to tail [OK]

Common Mistakes:

• Not updating pointers correctly
• Leaving last node pointing to old next
• Confusing original and reversed order

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

Node* reverse(Node* head) {
  Node* prev = NULL;
  Node* curr = head;
  while (curr != NULL) {
    Node* next = curr->next;
    curr->next = prev;
    prev = curr;
    // Missing update of curr here
  }
  return prev;
}

medium

A. prev is not initialized to NULL

B. The function returns head instead of prev

C. next pointer is not declared

D. The pointer curr is never updated inside the loop, causing an infinite loop

Solution

1. Step 1: Check loop pointer updates

   Inside the loop, curr must move to next node to avoid infinite loop.

2. Step 2: Identify missing update

   The code misses 'curr = next;' causing curr to never change and loop forever.

3. Final Answer:

   The pointer curr is never updated inside the loop, causing an infinite loop -> Option D

4. Quick Check:

   Missing curr update = infinite loop [OK]

Hint: Always move current pointer forward inside the loop [OK]

Common Mistakes:

• Forgetting to update curr
• Returning wrong pointer
• Not initializing prev

5. Given a singly linked list with nodes containing values [10, 20, 30, 40, 50], which of the following code snippets correctly reverses the list iteratively and returns the new head?

hard

A. Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr != nullptr) { curr->next = prev; prev = curr; } return prev; }

B. Node* reverseList(Node* head) { Node* curr = head; Node* prev = nullptr; while (prev) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return curr; }

C. Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; }

D. Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr != nullptr) { Node* next = curr->next; prev = curr; curr = next; } return prev; }

Solution

1. Step 1: Check pointer initialization and loop condition

   Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } initializes prev to nullptr, curr to head, and loops while curr is not null.

2. Step 2: Verify pointer updates inside loop

   Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } saves next, reverses curr->next, moves prev and curr forward correctly, then returns prev as new head.

3. Final Answer:

   Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } -> Option C

4. Quick Check:

   Correct pointer updates and return [OK]

Hint: Save next, reverse link, move prev and curr forward [OK]

Common Mistakes:

• Wrong loop condition
• Not saving next before changing links
• Returning wrong pointer