GO Classes DPP | GATE CS | Data Structures | Linked List Reverse

Answer 1

To reverse a singly linked list, every node must be visited once because each node’s $\texttt{next}$ pointer may need to be changed. 

This gives a lower bound of $\Omega(n)$.

Using three pointers, $\texttt{prev}$, $\texttt{curr}$, and $\texttt{next}$, the list can be reversed in one traversal. 

Therefore, the time complexity is $O(n)$.

Correct answer : A

Answer 2

A. Correct. There is a $O(n)$ time method to reverse a singly linked list.
B. Incorrect. It cannot be reversed in $O(\log n)$ time because there are $O(n)$ links to be updated.
C. Incorrect. It need not take $O(n^2)$ time since we already know a method to do it $O(n)$ time.
D. Incorrect. It is possible to reverse a singly linked list in-place.

Answer: A