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:

Trace the recursive call on a short list (say 3 nodes) for each option and check both whether the recursion terminates and whether the returned count is correct.

Answer 1

The Correct Option is B

Step 1: Understand what the function must do.
getListSize(head) must return the number of nodes in the list starting at head, and the problem states the list is always non-empty when the function is called from outside. The base case should fire exactly when the list has exactly one node left to count, and the recursive case should count the current node and recurse on the rest of the list.
Step 2: Identify the correct base case E1.
A list has exactly one remaining node when that node's next pointer is NULL, i.e. when head->next == NULL. Testing head == NULL instead is wrong for two reasons: first, the base case would never fire on the very last real node (its next is NULL, but the node itself is not NULL), so the recursion would try to go one node too far; second, if head==NULL is ever reached in a call, the correct count for an empty remainder is 0 nodes, not 1, so returning 1 there overcounts by one. So E1 must be head->next == NULL, ruling out options (A) and (C), whose E1 is head == NULL.
Step 3: Identify the correct recursive case E2.
Once E1 is false, the current node is not the last node, so the function must count the current node (contributing 1) plus the size of the rest of the list starting at the next node, which is getListSize(head->next). So E2 must be 1 + getListSize(head->next). Calling getListSize(head) again with the same, unchanged pointer does not move to the next node at all, so it cannot converge.
Step 4: Trace option (B), E1: head->next==NULL, E2: 1+getListSize(head->next), on a 3 node list A to B to C, where C->next is NULL.
getListSize(A): A->next is B, not NULL, so return 1+getListSize(B).
getListSize(B): B->next is C, not NULL, so return 1+getListSize(C).
getListSize(C): C->next is NULL, so return 1.
Unwinding: getListSize(B) = 1+1 = 2, getListSize(A) = 1+2 = 3, which is the correct size of the 3 node list.
Step 5: Show why option (A) fails.
E1: head==NULL is false for node A (A is not NULL), so it executes E2: 1+getListSize(head), calling itself again with the exact same argument head=A. Since head is never advanced to head->next anywhere in this option, every subsequent call also has head=A, E1 stays false forever, and the recursion never terminates, it just keeps calling itself with the same pointer until the call stack overflows. Option (A) is therefore not a valid implementation for any list with more than one node.
Step 6: Show why option (D) fails.
Option (D) has a correct base case, head->next==NULL, but E2 is 1+getListSize(head), which again passes the unchanged head pointer instead of head->next. Once the recursive branch is taken (list has 2 or more nodes), the argument never changes, head->next is still not NULL on every subsequent call, and the recursion never reaches the base case, again causing infinite recursion and a stack overflow.
Step 7: Show why option (C) fails.
Option (C) correctly advances the pointer in E2, 1+getListSize(head->next), but its base case is head==NULL, so on the 3 node example above it would recurse one call past the last node: getListSize(C) tests C==NULL (false), so it returns 1+getListSize(C->next) = 1+getListSize(NULL); getListSize(NULL) tests NULL==NULL (true) and returns 1. So getListSize(C)=1+1=2 instead of 1, and unwinding gives getListSize(A)=1+(1+2)=4 for a list that actually has only 3 nodes, an off by one overcount caused by counting the NULL terminator as an extra node.
Step 8: Conclusion.
Only option (B) both terminates for every non-empty list and returns the exact node count, matching the manual trace in Step 4.\[ \boxed{\text{Option (B): E1: head->next==NULL,\ \ E2: 1+getListSize(head->next)}} \]