GATE 2026 CS1 Q.39: solution and answer

GATE 2026 · CS1Q.39 · 2 marks · MCQ

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.

struct node{
  int elt;
  struct node *next;
};

int getListSize (struct node *head)
{
  if( E1 ) return 1;
  return E2;
}

Which one of the following options gives the correct replacements for the expressions E1 and E2?

(A)
E1: head == NULL
E2: 1 + getListSize(head)
(B)
E1: head->next == NULL
E2: 1 + getListSize(head->next)
(C)
E1: head == NULL
E2: 1 + getListSize(head->next)
(D)
E1: head->next == NULL
E2: 1 + getListSize(head)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct answer is option (B): E1 is head->next == NULL and E2 is 1 + getListSize(head->next).

Official answer: BSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

The function is documented to be called only on a non-empty list, so head is never NULL at the point of the call — the base case must detect the LAST node reached during recursion, not a NULL head.
The last node in the list satisfies head->next == NULL, and that single node contributes exactly 1 to the total count. So the base case should be E1: head->next == NULL, returning 1 there.
For any non-last node, the recursive step must add 1 for the current node and advance the pointer to the next node so the recursion makes progress: E2: 1 + getListSize(head->next).
Rule out (A): E1 = head==NULL, E2 = 1+getListSize(head). The recursive call passes head unchanged, so the pointer never advances — this recurses forever on the same node (stack overflow), never terminating.
Rule out (D): E1 = head->next==NULL, E2 = 1+getListSize(head). Same flaw as (A): the recursive call never advances the pointer, causing infinite recursion.
Rule out (C): E1 = head==NULL, E2 = 1+getListSize(head->next). Trace a 3-node list A->B->C->NULL: getListSize(A) = 1+getListSize(B) = 1+(1+getListSize(C)) = 1+(1+(1+getListSize(C->next=NULL))); getListSize(NULL) hits head==NULL and returns 1. Total = 1+1+1+1 = 4, but the list has only 3 nodes — this makes one extra call past the last node into NULL, overcounting by 1.
Check (B): E1 = head->next==NULL, E2 = 1+getListSize(head->next). Trace the same 3-node list: getListSize(A): A->next=B≠NULL, so 1+getListSize(B); getListSize(B): B->next=C≠NULL, so 1+getListSize(C); getListSize(C): C->next==NULL (last node), returns 1 directly. Total = 1+1+1 = 3 — matches the true node count.
Sanity check the single-node case for (B): head->next==NULL holds immediately, so the base case fires at once and returns 1 — correct.
Therefore (B) is the only option that both terminates and computes the correct count.

KEY IDEA

A recursive size/length function over a linked list needs its base case and recursive step to move in lockstep: the base case must fire exactly once per traversal (at the true last node, detected by head->next == NULL, not by overshooting to head == NULL), and the recursive call must always advance the pointer it tests (getListSize(head->next), never the unchanged head) or it never terminates.

WATCH OUT FOR

Picking option (C) (E1: head==NULL, E2: 1+getListSize(head->next)) — this looks like the "natural" NULL-terminated recursion pattern but it makes one extra call past the last node (into NULL), overcounting every list by exactly 1. Equally common is picking (A) or (D) where E2 recurses on the unchanged head pointer, causing infinite recursion / a crash rather than a wrong count.

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

GATE 2026 CS1 Q.39: solution and answer

Answer and solution

More Linear structures questions