Consider the problem of reversing a singly linked list. To take an example,…
2022
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.
Attempted by 385 students.
Show answer & explanation
Correct answer: A
Solution: Reverse the list in-place by changing next pointers as you traverse the list.
Initialize three pointers: prev = null, curr = head.
While curr is not null, do:
Save next = curr.next.
Set curr.next = prev to reverse the pointer.
Move prev = curr and curr = next.
After the loop, set head = prev. The list is now reversed.
Complexity analysis:
Time: Θ(n) because each node is visited exactly once and a constant number of pointer operations are done per node.
Space: O(1) extra space because only a constant number of pointer variables (prev, curr, next) are used.
Lower bound: Ω(n) since any algorithm that produces the reversed list must examine every node at least once, so the running time is Θ(n).
Note: A recursive reversal can also produce a reversed list but uses O(n) call stack space; the iterative method is preferred when O(1) extra space is required.
A video solution is available for this question — log in and enroll to watch it.