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 $\text{TRUE}$ about the time complexity of algorithms that solve the above problem in $O(1)$ space?
- 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.
