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?
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.
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.
More Linked Lists questions
GATE 2020 CS Q26– What is the worst case time complexity of inserting n elements into an empty linked list,…
GATE 2017 CS (CS1) Q18– Consider the C code fragment given below. Assuming that `m` and `n` point to valid…
GATE 2016 CS (CS2) Q25– N records are in a sorted doubly linked list. Node pointers are supplied for delete and…
GATE 2017 CS (CS2) Q23– A circular queue uses a singly linked list, with value and next-pointer per node and…
GATE 2010 CS Q46– For a singly linked list with at least two nodes, fill the blank to move its last node to…