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 (n) time in the worst case. B) The best algorithm for the problem takes (n n) time in the worst case. C) The best algorithm for the problem takes (n2) time in the worst case. D) It is not possible to reverse a singly linked list in O(1) space.

Official answer: A) The best algorithm for the problem takes (n) time in the worst case.. Explanation: A singly linked list with n nodes can be reversed in-place using three pointers (`prev`, `curr`, `next`) in O(1) auxiliary space. In this iterative algorithm: - We iterate through each node once from head to tail. - At each step, the `next` pointer of the current node is reversed to point to `prev`. - A total of n nodes are visited and processed in constant time per node. Thus, the algorithm runs in (n) (or (n)) time in the worst case using O(1) space. Since every node's pointer must be modified, (n) is also the lower bound, making (n) the best possible time complexity. Therefore, option A is the correct statement.

A) The best algorithm for the problem takes (n) time in the worst case.

B) The best algorithm for the problem takes (n n) time in the worst case.

C) The best algorithm for the problem takes (n2) time in the worst case.

D) It is not possible to reverse a singly linked list in O(1) space.

Programming and Data Structures · Linear Structures, Trees and Heaps

Official IIT answer key · IIT Kharagpur · Audited Aug 2026

Take topic test

GATE CSE 2022 Q15 · MCQ · 1 mark

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?

Select an option to check

Key concept

Linear Structures, Trees and Heaps

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Linear Structures, Trees and Heaps

Across the provided GATE CS papers, this topic evaluates foundational data structures with an emphasis on implementation mechanics, boundary conditions, and asymptotic time complexities of core and advanced operations. Earlier questions focus directly on array-based circular queue pointer conditions and basic operation bounds (O(1) enqueue/dequeue). Recent questions test deep algorithmic understanding of multi-step operations like melding across disparate data structures such as doubly linked lists, binary heaps, and binary search trees.

Full Linear Structures, Trees and Heaps guide →

More on Linear Structures, Trees and Heaps

All 14 questions on Linear Structures, Trees and Heaps →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Programming and Data Structures · Linear Structures, Trees and Heaps

Official IIT answer key · IIT Kharagpur · Audited Aug 2026

Take topic test

GATE CSE 2022 Q15 · MCQ · 1 mark

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?

Select an option to check

Key concept

Linear Structures, Trees and Heaps

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Linear Structures, Trees and Heaps

Full Linear Structures, Trees and Heaps guide →

More on Linear Structures, Trees and Heaps

All 14 questions on Linear Structures, Trees and Heaps →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in $O(1)$ space?

Step-by-step verified solution

Check you can still solve Linear Structures, Trees and Heaps under a clock

More from GATE CSE 2022

More on Linear Structures, Trees and Heaps

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in $O(1)$ space?

Step-by-step verified solution

Check you can still solve Linear Structures, Trees and Heaps under a clock

More from GATE CSE 2022

More on Linear Structures, Trees and Heaps

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1)O(1)O(1) space?

Step-by-step verified solution

Check you can still solve Linear Structures, Trees and Heaps under a clock

More from GATE CSE 2022

More on Linear Structures, Trees and Heaps

Share this solution

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1)O(1)O(1) space?

Step-by-step verified solution

Check you can still solve Linear Structures, Trees and Heaps under a clock

More from GATE CSE 2022

More on Linear Structures, Trees and Heaps

Share this solution

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in $O(1)$ space?

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in $O(1)$ space?