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 and
View worked solution
Answer: B
To find the size of a non-empty singly linked list recursively, we define a base case and a recursive step:
- Base Case: Since the list is guaranteed to be non-empty, the smallest possible list has exactly node. For a single-node list, the next pointer is
NULL(i.e.,head->next == NULL). In this case, the function should return . Thus, E1 must behead->next == NULL. - Recursive Step: If the list has more than one node, the total size is (for the current head node) plus the size of the remaining list starting from the next node. Thus, E2 must be
1 + getListSize(head->next).
Let's verify why the other options are incorrect:
- Option A & D: The recursive call uses
headinstead ofhead->next, which results in infinite recursion (stack overflow). - Option C: If
E1ishead == NULL, then a list with node would call1 + getListSize(NULL). SincegetListSize(NULL)returns (due to the base case), the total size returned for a -node list would be , which is incorrect.
Therefore, the correct replacements are given by Option B.
Free practice · Your answers on this page are not saved.