Skip to content
GATEiit

GATE CSE 2022 Q15: Time to reverse a singly linked list in O(1) space

Question

Consider the problem of reversing a singly linked list. To take an example, given the linked list in the top row of the figure, the reversed linked list should look like the bottom row.

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

Top row: head pointing to the list a, b, c, d, e ending in null. Bottom row: head pointing to the reversed list e, d, c, b, a ending in null
Tap the figure to enlarge

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2022 final answer key)

Concept used: In-place reversal with three pointers (previous, current, next) visits each node once.

First step: Walk the list once, redirecting each node's next pointer to the previous node.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key

More Programming and Data Structures PYQs

PracticePractise Programming and Data Structures questions →Full paperAll GATE CSE 2022 questions →