GATE 2026 CS (CS1) – Question 39
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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) E1: head->next == NULL; E2: 1 + getListSize(head->next)
Explanation
The problem specifies that the singly linked list is non-empty (`head != NULL`).
- In the recursive definition of list size with a base return value of 1:
A single-node list has size 1. The condition identifying a single-node list is when the node has no successor, which is `head->next == NULL`. Hence, `E1` must be `head->next == NULL`.
- For a list with more than 1 node, the total size is 1 (for the current node) plus the size of the rest of the list starting from the next node: `1 + getListSize(head->next)`. Hence, `E2` must be `1 + getListSize(head->next)`.
Option (A) and (C) fail because if `head == NULL`, returning 1 would incorrectly report a size of 1 for an empty list, and option (A) causes infinite recursion. Option (D) causes infinite recursion.
Therefore, option (B) is correct.