The GATE Grind

GATE 2022 CS – Question 15

Programming and Data Structures · Linked Lists · 1 mark · Multiple choice

Consider the problem of reversing a singly linked list. To take an example, given the linked list a → b → c → d → e, the reversed linked list should look like e → d → c → b → a.
Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in $O(1)$ space?

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) The best algorithm for the problem takes $\theta(n)$ time in the worst case.

Explanation

Iterative pointer reversal with three pointers (prev, curr, next) takes $\theta(n)$ time and $O(1)$ space. Every node must be visited, so $\Omega(n)$ is also needed.