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

Step 1: Understand the recursive structure needed. The function getListSize should count nodes in a non-empty singly linked list. A correct recursive definition needs a base case that stops recursion right at the last node, and a recursive case that adds 1 for the current node and recurses on the rest of the list.

Step 2: Identify the correct base case E1. Since the list is guaranteed non-empty, the recursion should stop when the current node is the last node, i.e. when head->next == NULL. At that point there is exactly 1 node left to count, so it returns 1.

Step 3: Identify the correct recursive case E2. If head->next is not NULL, the current node contributes 1, and the rest of the count comes from recursing on the remaining list starting at head->next. So E2 is 1 + getListSize(head->next).

Step 4: Rule out the other options. Using head == NULL as the base case (options A and C) only becomes true one call past the last node, forcing that final call to dereference NULL->next when combined with the recursive step that advances via head->next, which crashes. Option D reuses E2 = 1 + getListSize(head), which never advances the pointer and recurses forever.

Step 5: Confirm with a small example. For a 3-node list A->B->C->NULL: call on A, since A->next is not NULL, return 1 + getListSize(B); call on B, since B->next is not NULL, return 1 + getListSize(C); call on C, since C->next == NULL, return 1. Total = 1+1+1 = 3, the correct count.

Final Answer: E1 is head->next == NULL and E2 is 1 + getListSize(head->next). \(\boxed{\text{Option B}}\)