Project ForgeData Structures
Arrays & Linked Lists
GATE 2022
Easy
Consider the problem of reversing a singly linked list. Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?
- The best algorithm for the problem takes Θ(n) time in the worst case.
- BThe best algorithm for the problem takes Θ(n log n) time in the worst case.
- CThe best algorithm for the problem takes Θ(n²) time in the worst case.
- DIt is not possible to reverse a singly linked list in O(1) space.
Explanation
The standard iterative 3-pointer technique (prev, curr, next) reverses a singly linked list of n nodes using only O(1) extra space, visiting each node exactly once to flip its 'next' pointer — Θ(n) time, and this is optimal since every node must be touched at least once.
Source: GATE CS 2022 (2022)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.