Question:

Consider the problem of reversing a singly linked list. To take an example, given the linked list below, 

The reversed linked list should look like 

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in \( O(1) \) space?

Show Hint

Reversing a singly linked list can be done efficiently in \( \theta(n) \) time with \( O(1) \) space.
Updated On: Jan 30, 2026
  • The best algorithm for the problem takes \( \theta(n) \) time in the worst case.
  • The best algorithm for the problem takes \( \theta(n \log n) \) time in the worst case.
  • The best algorithm for the problem takes \( \theta(n^2) \) time in the worst case.
  • It is not possible to reverse a singly linked list in \( O(1) \) space.
Hide Solution
collegedunia
Verified By Collegedunia

The Correct Option is A

Solution and Explanation

Reversing a singly linked list involves iterating through the list once and changing the direction of the pointers. The best algorithm for this problem runs in linear time \( \theta(n) \), where \( n \) is the number of elements in the list. Since we are only using a constant amount of extra space (just a few pointers to help with reversal), the space complexity is \( O(1) \).
Thus, the time complexity is \( \theta(n) \) in the worst case.
Was this answer helpful?
0
0

Top Questions on Linked Lists

View More Questions

Questions Asked in GATE CS exam

View More Questions