UPPCL AE 2018:60

Question

The following function attempts to merge two sorted linked lists. ListNode is the custom structure representing a node in the linked list.

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode* pMergedHead = NULL;
if (pHead1->m_nValue < pHead2->m_nValue) {
pMergedHead = pHead1;
pMergedHead->m_pNext = Merge (pHead1->m_pNext, pHead2);
} else if (pHead1->m_nValue > pHead2->m_nVlaue) {
pMergedHead = pHead2;
PMerged->m_pNext = Merge(pHead1, pHead2->m_pNext);
}
return pMergedHead;
}

Assume that the inputs lists are correctly sorted. Which of the following are some of the possible behaviors when the code is executed with well-formed and valid inputs?

1.     The code snippet can produce a correctly merged linked list.
2.     The code snippet can lead to a segmentation fault.
3.     The code snippet can result in an incorrectly merged linked list.

• A. $\text{I, II} $ and $\text{III}$
• B. $\text{II} $ and $\text{III}$
• C. $\text{I} $ and $\text{III}$
• D. $\text{I}$ only

Answer 1

We're not checking, after entering the $merge$ function or before calling $merge$ function, if $pHead1$ or $pHead2$ are $NULL$ or NOT. 

This may lead to runtime error (segmentation fault).

Now, we'll try to understand what the $merge$ function does to further evaluate it's behaviour -

1. We'll call the nodes pointed by $pHead1$ and $pHead2$ as $curr1$ and $curr2$ for simplicity.
2. When $curr1$ is smaller, we set $curr1.next$ equal to whatever $merge$ returns when $merge$ is called on $curr1.next$ and $curr2$ and at last it returns $curr1$.
3. When $curr2$ is smaller, we set $curr2.next$ equal to whatever $merge$ returns when $merge$ is called on $curr2.next$ and $curr1$ and at last it returns $curr2$.
4. When both $curr1$ and $curr2$ are equal, $merge$ returns $NULL$.

So, there is a case when the recursive calls end and doesn't produce an error. Now the question is does it produce correctly merge list.

$\implies no$, since it may happen that some nodes are there after the nodes with common values, those nodes will not be linked to our resultant list. Even both the nodes with equal values will not be linked to our resultant list.

We may get incorrectly merged list.

Answer :- B.

If anyone wants to try -

List1 : $2 - 3 - 5 - 7 - null$

List2 : $1 - 5 - 10 - null$

Answer 2

Option A is correct.

It is an attempt to implement mergesort recursively. The idea is, at any point, if we are given two heads of two linked lists, we will compare the values of these two heads, order them as smallest one first then its next pointing to the larger one and then, we will call the merge function with the remaining lists. Means, we call the merge function with head1.next, head2.next , so that the remaining list is merged and head of the combined list is returned. So here in the actual call, we are ordering nodes as smaller one first, larger one second and then we will link this to returned head of remaining list of recursive call. When any of the one list ends, we stop the recursive call, and simply concatenate the remaining list to point , because both lists are already sorted. so it acts a base case.

But it has mistake that, It doesn’t include the case of = (equal to) in comparison, that would lead to problem. and also it lacks checks for null values which can lead to runtime error. as explained in other answers.

So, II is true, it can show runtime error.

III is also true as it produces incorrect results , when there is any value common between two lists (returns a short list)
 

and I is also true, it can produce correct results too, if there is no value common between the two lists. so it produces correct results sometimes.

so Option A, I, II, III are correct.

Comments

@Lotan Chatterjee if statement $1$ is True can you give an example of non-empty lists on which $merge$ function will successfully, without error, produce correctly merged list.

Answer 3

if lists are reverse sorted it can give incorrect results

Comments

In question is already given that boths input lists are correctly sorted.