Register
Dark Mode

GO Classes Weekly Quiz 9 | Data Structures | Linked List | Question: 2

in DS recategorized by
742 views
7 votes
7 votes

Consider the following function Merge() that takes the head of two linked lists.

struct node {
    int value;
    struct node *next;
};
typedef struct node Node;

Node * Merge(Node * head1, Node * head2) {
    if (head1 == NULL) return head2;
    if (head2 == NULL) return head1;
    Node * head = NULL;
    if (head1 -> value < head2 -> value) {
        head = head1;
        head -> next = Merge(head1 -> next, head2);
    }
    else if (head1 -> value > head2 -> value) {
        head = head2;
        head -> next = Merge(head1, head2 -> next);
    }
return head;
}

Assume that the input lists are correctly sorted. Which of the following are some of the possible behaviors when Merge() is executed with well-formed and valid inputs?. Correctly merged linked list is merged sorted linked list.

  1. The function will produce a correctly merged linked list.
  2. The function may lead to a null pointer dereference.
  3. The function may result in an incorrectly merged linked list.
  4. Merge() will work on following two lists.
    $\text{List}1: 1 \rightarrow 3 \rightarrow 5\rightarrow 7\rightarrow \text{Null}$
    $\text{List}2: 2\rightarrow 4\rightarrow 6\rightarrow 8\rightarrow 10 \rightarrow 12\rightarrow \text{Null}$
in DS recategorized by
by
742 views

2 Answers

12 votes
12 votes

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.

by

4 Comments

by
In this question, well formed means that the 2 linked lists do not have the same value because if they do for ex(1->2) is list 1 and (1->5) is list 2 then it is also possible that the pointer returns null or head returns null? So option B is also possible right?
0
0
by
Yes, it is possible that merge will return null. But we're not dereferencing the returned pointer. So no NULL pointer dereference error.
1
1
by
Okay, so here head is  a pointer which stores the address of the struct node which in this case is null and return type of this function is a pointer to node. If we had dereferenced the pointer somewhere in the code as in head is pointer to struct node and if we dereference it this means that we are accessing NULL , then it would have NULL pointer dereference. So there is no error if we are not dereferencing it. Is my understanding correct?
0
0
by
Yes
0
0
3 votes
3 votes

This question involves recursion so it needs a careful track of every link . 

First Step after reading out the Options,We can try out the Option 4 to check whether the List is correctly merged or not. 

Take smaller version of the given example and trace out the recursion.

List1 : 1-->3

List 2 : 2-->4

if you trace the recursion carefully, it results in correctly merged list as 1-->2-->3-->4

So merge function is working well in this example because of the property of elements being distinct in both the lists. In every comparision either if() is true or else if() is true.

So,Option D can be considered as one of the answer.

Lets move to analysing Option A,B,C

Since you got the correct merged list,you will mostly consider Option A aswell. But Stop we have to think about differrent kind of inputs possible right? 

if we take 2 lists were some of the elemets are common to both of the lists and if it is correctly merged,then we can say option A is true and Option C is false.

Let List 1: 1-->3

      List 2: 1-->3.-->4

the result should be 1-->3-->4

but the moment you enter the function your head = NULL neither of If () is true due to the fact that the function is not taking care of elemets whose elemets are equal. So in this case its returning NULL. 

So we can say Option A is False and Option C is true.

Till now Options C,D are true and  Option A is false.

Lets check about option B.

It says 

  1. The function may lead to a null pointer dereference. null pointer dereference happens when we access the pointer pointing to NULL. Lets chack whether it is true according to giveen function. For this we need to check the accessing points where we are accessing the values for manipulations. We are accessing the values in if() and else if() and in both we are accessing the values present in each node . Since we are checking if( head1 == NULL ) and if(head2==NULL) which will return if condition is true,  in the begin of function,there is no chance of accessing the null pointer. So option B is also false. 

 

So Option C,D are the true ones which causes problem in merge() function. 

 

Tip:If you can observe the merger() function not handling the equality of elemets , you can easily eliminate Option A without any analysis In this case Option C is correct.So You are left with checking only B,D. 

 

by
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

Subscribe to GATE CSE 2023 Test Series

Subscribe to GO Classes for GATE CSE 2023

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Developed by Chun
Link Copied!