IAE Academy

GATE 2022 CS Q.15: solution and answer

GATE 2022 · CSQ.15 · 1 mark · MCQ

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

head → [a|•]→ [b|•]→ [c|•]→ [d|•]→ [e|•]→ (null, shown as ground symbol)

the reversed linked list should look like

head → [e|•]→ [d|•]→ [c|•]→ [b|•]→ [a|•]→ (null, shown as ground symbol)

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

GATE 2022 CS question 15: Two horizontal singly linked list diagrams, each a chain of 5 boxes.Tap to open full size
Figure from the GATE 2022 CS paper. It is part of the question.
Figure description

Two horizontal singly linked list diagrams, each a chain of 5 boxes. Each box is drawn as a two-cell node: left cell holds a data value, right cell holds a pointer (drawn as a small vertical bar with an arrow leaving it to the next node). Top diagram (original list): 'head' with an arrow into node containing 'a', arrow to node 'b', arrow to node 'c', arrow to node 'd', arrow to node 'e', and the last node's pointer cell points to a ground/earth symbol (⏚) denoting NULL. Bottom diagram (reversed list): identical structure but with values in order 'head' → e → d → c → b → a → NULL (ground symbol). This just illustrates that the list a-b-c-d-e becomes e-d-c-b-a after reversal.

  1. (A)

    The best algorithm for the problem takes time in the worst case.

  2. (B)

    The best algorithm for the problem takes time in the worst case.

  3. (C)

    The best algorithm for the problem takes time in the worst case.

  4. (D)

    It is not possible to reverse a singly linked list in space.

Answer and solution

ANSWER

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

Official answer: ASource: Official answer key, GATE 2022 CS (IIT Kharagpur)

  1. Restate the problem: reverse a singly linked list a→b→c→d→e into e→d→c→b→a using only O(1) extra space (no auxiliary array/list, no recursion stack).

  2. Standard iterative in-place algorithm: prev = NULL, curr = head; while curr != NULL: { next = curr->link; curr->link = prev; prev = curr; curr = next; } — this uses exactly three pointer variables, independent of list size, so extra space is O(1).

  3. Trace the loop: at each iteration exactly one node's link field is redirected from its old successor to the previous node, and the three pointers each advance by one position; each iteration does a constant number of operations.

  4. The loop executes exactly n times, once per node, since curr steps through the whole list from head to NULL — so the total running time is Θ(n) (both O(n) and Ω(n)).

  5. Lower bound argument: to correctly reverse the list, every node's link field must be inspected and rewritten at least once (any node left untouched would still point the old way), so no algorithm — regardless of space usage — can run in better than Θ(n) time. This confirms Θ(n) is the best (tight) achievable bound, not just an upper bound.

  6. Check against the options: (A) Θ(n) — matches exactly. (B) Θ(n log n) and (C) Θ(n²) both claim slower tight bounds than what is achievable, so both are false. (D) is false since the O(1)-space, Θ(n)-time algorithm above exists.

  7. Conclusion: option (A) is TRUE.

KEY IDEA

A singly linked list can be reversed in-place using three pointers (prev, curr, next), touching each node exactly once — this gives time using only extra space, and no algorithm can do better than since every node's link must be inspected and changed at least once.

WATCH OUT FOR

Assuming an -space constraint forces a slower algorithm (choosing B, C, or D) because students associate space-restricted algorithms with recursion (which needs stack space) rather than the standard iterative three-pointer technique, which needs only constant extra space and still runs in linear time.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 13 Linear structures questions, with notes

More Linear structures questions