Question

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)

Hint:

The base case must stop one node before the end (checking head->next == NULL), and the recursive call must move to head->next, not stay at head, otherwise the recursion never terminates or dereferences NULL.

Answer 1

The Correct Option is B

Alternative approach - trace pointer movement. Step 1: Think of the recursion as a pointer that must move forward by one node at every call, otherwise it can never terminate. Only E2 = 1 + getListSize(head->next) advances the pointer; E2 = 1 + getListSize(head) keeps calling with the same head forever, causing a stack overflow, so option D is eliminated immediately. Step 2: Now decide between checking head == NULL or head->next == NULL as the stopping condition. If the base case were head == NULL, the recursive step would need to be called one more time after reaching the last node, meaning it would evaluate NULL->next inside that extra call - an invalid dereference that crashes the program. Step 3: So the base case must catch the last node one step earlier, using head->next == NULL. This check is always safe because head itself is guaranteed non-NULL at every call - the list starts non-empty and every recursive call passes a genuine node pointer, never NULL. Step 4: With base case head->next == NULL returning 1, and recursive case 1 + getListSize(head->next), every call operates on a valid non-NULL node, and the recursion depth exactly equals the number of nodes. Step 5: Sanity check on a single-node list: head->next is NULL immediately, so the function returns 1 without ever recursing further - correct. Final answer: E1 is head->next == NULL and E2 is 1 + getListSize(head->next), option B.