The input to merge() is two pointer of type node.
(For the sake of this discussion we’ll limit ourselves to only discuss the case where both pointers belong to different LL).
When both pointers are not NULL, the function creates a new pointer “head” which copies the address of one of the input pointer which points to some node that has strictly lesser value than that of the other and returns this “head” pointer.
This means the merge() will always returns the pointer to the node which has strictly lesser value out of the two node pointers that it received.
Then merge() calls itself with the pointer of next node of selected node and same pointer of other node and merge() will save whatever address of the next merge() call returns in current head->next.
This means the merge() will recursively keep rearranging the resultant LL such that the order is always strictly increasing.
(We’ll see why this strictly word comes in again and again later)
When one of the pointers is NULL, then merge() returns the other pointer.
This means there are no more elements in one of the LL so it simply returns the other LL node pointer. Since, both input LL are already sorted, there’s no need to check further. It directly appends the remaining nodes of non-empty LL into the resultant LL.
When both the pointers are NULL, then merge() returns NULL.
This means there are no more elements in both LL, so it returns NULL.
Both the above conditions are our base case conditions to end the recursion (in favorable conditions).
*** So far so good ***
Now, suppose both input pointers point to some node with have same value. Then both if and else if condition will fail. And we’ll directly return NULL (since no assignment happened to head).
This means if both LL has distinct values in their nodes then the merge() correctly merges both LL in sorted order.
But if both LL has at least one value common in their nodes. Then resultant LL will only contain nodes which are less than that common value.
For example –
List1 → 2 → 4 → 6 → 8 → 10 → 12 → NULL
List1 → 5 → 10 → 15 → 20 → 25 → NULL
List = merge(List1, List2)
Then List → 2 → 4 → 5 → 6 → 8 → NULL
Answer :- C, D.