Reverse a Singly Linked List Iterative in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind reversing a singly linked list iteratively?

We change the direction of the links between nodes one by one, using three pointers: previous, current, and next. This way, we reverse the list without creating new nodes.

beginner

In the iterative reversal of a singly linked list, what role does the 'previous' pointer play?

The 'previous' pointer keeps track of the node that should come after the current node once the link is reversed. It helps to redirect the current node's next pointer backward.

beginner

Why do we need a 'next' pointer during the iterative reversal of a singly linked list?

The 'next' pointer temporarily stores the next node before changing the current node's next pointer. This prevents losing access to the rest of the list during reversal.

beginner

What is the time complexity of reversing a singly linked list iteratively?

The time complexity is O(n), where n is the number of nodes, because we visit each node exactly once to reverse the links.

beginner

What is the space complexity of the iterative method to reverse a singly linked list?

The space complexity is O(1) because we only use a fixed number of pointers regardless of the list size.

Which pointer is used to keep track of the node that will become the new head after reversal?

A previous

B current

C next

D head

The 'previous' pointer moves along the list and ends up pointing to the new head after reversal.

What happens to the 'next' pointer of the original head node after reversal?

A It points to the second node

B It points to itself

C It points to null

D It points to the previous node

After reversal, the original head becomes the tail, so its next pointer points to null.

How many times does the loop run in the iterative reversal of a singly linked list with n nodes?

A n+1 times

B n times

C n-1 times

D Depends on the list

The loop runs exactly n times, once for each node.

Which of these is NOT needed to reverse a singly linked list iteratively?

A A pointer to the previous node

B A pointer to the current node

C A pointer to the next node

D A stack to store nodes

No extra data structures like a stack are needed; only pointers are used.

What is the final step after the loop finishes in iterative reversal?

A Return the previous pointer as the new head

B Return the current pointer as the new head

C Return the next pointer as the new head

D Return the original head

After the loop, 'previous' points to the new head of the reversed list.

Explain step-by-step how to reverse a singly linked list using an iterative approach.

Think about how you change the direction of each link one by one.

Describe the roles of the three pointers used in iterative reversal of a singly linked list.

Each pointer helps to keep track of nodes during reversal.

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