Consider the problem of reversing a singly linked list in O(1) space. Which one of the following sta

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2022 GATE-CS Data Structures paper.

Q: How can I prepare for GATE-CS Data Structures?

To prepare for GATE-CS Data Structures, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2022 question covers Linked Lists topic.

Q: What is the difficulty level of this question?

This GATE-CS 2022 Data Structures question has a easy difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Consider the problem of reversing a singly linked list in O(1) space. Which one of the following statements is TRUE about the time complexity?

Accepted Answer

Correct Answer: (A) Theta(n) in the worst caseConcept -- Singly Linked List Reversal (from Cormen et al., Introduction to Algorithms):A singly linked list can be reversed in-place using O(1) extra space by maintaining three pointers: prev, current, and next. The algorithm traverses the list once, reversing each pointer:prev = NULL; current = head;
while(current != NULL) {
  next = current->next;
  current->next = prev;
  prev = current;
  current = next;
}
head = prev;This traverses all n nodes exactly once, performing O(1) work per node, giving Theta(n) total time. It is not possible to do better than Omega(n) since we must visit every node at least once (otherwise we cannot reverse the list correctly). Therefore the best possible algorithm takes Theta(n) time.

Consider the problem of reversing a singly linked list in O(1) space. Which one of the following statements is TRUE about the time complexity?

Master GATE-CS with Our Test Series

More Questions from Linked Lists

Frequently Asked Questions

Consider the problem of reversing a singly linked list in O(1) space. Which one of the following statements is TRUE about the time complexity?

Master GATE-CS with Our Test Series

More Questions from Linked Lists

Frequently Asked Questions