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?

• A. The best algorithm for the problem takes \( \theta(n) \) time in the worst case.
• B. The best algorithm for the problem takes \( \theta(n \log n) \) time in the worst case.
• C. The best algorithm for the problem takes \( \theta(n^2) \) time in the worst case.
• D. It is not possible to reverse a singly linked list in \( O(1) \) space.

Hint:

Reversing a singly linked list can be done efficiently in \( \theta(n) \) time with \( O(1) \) space.

Answer 1

The Correct Option is A

Reversing a singly linked list is done by traversing the list once and updating the next pointer of each node so that it points to its previous node instead of the next one.

Time Complexity:
Each node in the list is visited exactly once during the reversal process. If the list contains \( n \) nodes, the total number of operations grows linearly with \( n \). Hence, the time complexity in the worst case is: \[ \theta(n) \]

Space Complexity:
The algorithm uses only a constant number of extra pointers (for example, prev, curr, and next) regardless of the size of the list. No additional data structures are required. \[ O(1) \]

Thus, reversing a singly linked list can be done in linear time using constant extra space, and the worst-case time complexity is: \[ \theta(n) \]