GATE CS 2022 (Forenoon) — Question 15

Data StructuresLinked Lists & Binary TreesMCQ1 mark · −1/3 if wrongEasy

Consider the problem of reversing a singly linked list. To take an example, given the linked list below:
Question image
the reversed linked list should look like
Question image
Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in \(O(1)\) space?
  1. A
    The best algorithm for the problem takes \(\theta(n)\) time in the worst case.
  2. B
    The best algorithm for the problem takes \(\theta(n \log n)\) time in the worst case.
  3. C
    The best algorithm for the problem takes \(\theta(n^2)\) time in the worst case.
  4. D
    It is not possible to reverse a singly linked list in \(O(1)\) space.
Practise the full 2022-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAPractise this subject in the exam simulatorTimed, GATE-style tests with analytics that find your weak topics.
Practise more on Linked Lists & Binary TreesTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group