GATE CSE 2017 Set 1 | Question: 08

Question

Consider the C code fragment given below.

typedef struct node {
    int data;
    node* next;
} node;

void join(node* m, node* n) {
    node* p = n;
    while(p->next != NULL) {
        p = p->next;
    }
    p->next = m;
}

Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will

• A. append list m to the end of list n for all inputs.
• B. either cause a null pointer dereference or append list m to the end of list n.
• C. cause a null pointer dereference for all inputs.
• D. append list n to the end of list m for all inputs.

Comments

please include a tag "gate2017-1"

---

My interpretation of the question -

It is not mentioned explicitly that the lists are non-null. They are valid null-terminated implies if the list is non-empty the last node pointer successfully points to the null. Thus if the list n is itself NULL then dereferecing will create NULL pointer issue. Thus option b) Either null de-reference issue or appends list

---

any one challenging this question ??

---

Option B is correct answer as if node *n is inicially NULL then 

while(p->next != NULL)

will couse an error else list m append to the end of list n .

---

while(p->next != NULL),

when n is NULL,

the above stmt can be written as,

((*p).next != NULL) - this is null pointer dereference exception.

---

As it is stated in the question, that m and n are valid Lists but not explicitly specified if the lists are empty or not. We can have two cases:

1. Case 1: If lists are not NULL : Invocation of join will append list m to the end of list n if the lists are not NULL.      For Example:                                                                                                     Before join operation:          m=1->2->3->4->5->null;    n=6->7->8->9->null;                                                                                                          After join operation :                               6->7->8->9->1->2->3->4->5->null
2. Case 2: If lists are NULL : If the list n is empty and itself NULL, then joining and referencing would obviously create NULL pointer issue.

Therefore option B is correct

 

 

---

The answer to this question purely depends upon the interpretation of the English language(So I asked one of my English genius friend of the mechanical branch who is also aware of GATE pattern). The C code given in the question itself says that 'm' & 'n' are two pointers that stores the address of a structure of type 'node'. Now think about it, at any given instant in time, either pointer will be pointing to some address or it will be "NULL", but they explicitly mentioned the statement "Assuming that m and n point to valid NULL-terminated linked lists" before asking the actual question. It somehow indicates to us that we consider both pointers are pointing to linked lists before giving your answers because one can easily understand the function of 'm' & 'n' by looking at the code given. They didn't need to inform us about the function of the pointers otherwise there are many things to inform like "TypeDef"... So, in my opinion, the answer should have been option A only.

---

"Assuming that m and n point to valid NULL-terminated linked lists" – the line says  that the linked lists are not infinite they are finite ..

hence option B is correct.

---

@Rajatagrawal   firstly you need to have something to NULL-terminate. The statement points to the fact that the linked list will have atleast one node. (in my opinion, of course).

If $n$ is $NULL$, then it’s not even a linked list, but a just a pointer.

---

https://www.youtube.com/watch?v=GnqaL8K3v6o

Answer 1

Here is the implemented code in c (-std=c99).

#include <stdio.h>
#include <stdlib.h>

#define M 5
#define N 4

int M_data[M] = {1,2,3,4,5};
int N_data[N] = {6,7,8,9};

typedef struct node {
int data;
struct node * next;
}node;

void join(node *m,node *n) {
    node * p = n;
    while(p->next != NULL) p = p->next;
    p->next = m;
}

node * bulk_insert(int list_data[],int size) {
    node * head = NULL;
    for(int i=0;i<size;i++) {
        node * newnode = malloc(sizeof(node));
        newnode->data = list_data[i];
        newnode->next = NULL;

        if(head == NULL) {
            head = newnode;
        }else {
            node * temp = head;
            while(temp->next != NULL) temp = temp->next;
            temp->next = newnode;
        }
    }
    return head;
}
void display(node *);
void list_dealloc(node *); /*deallocation prototype*/

int main() {
    node * m = NULL;
    node * n = NULL;
    // insert m_list data
    m = bulk_insert(M_data,M);
    n = bulk_insert(N_data,N); // commenting this causes runtime error
    // is list n is empty
    printf("\n before join operation :\n");
    display(m);
    display(n);

    join(m,n);

    printf("\n after join operation :\n");
    display(m);
    display(n);

    //list_dealloc(m); no need now
    list_dealloc(n); // OK
    return 0;

}

void display(node *head) {
    while(head != NULL) {
        printf("%d->",head->data);
        head = head->next;
    }
    printf("null\n");
}
void list_dealloc(node * head) {
    while(head != NULL) {
        node * temp = head;
        head = head->next;
        free(temp);
    }
}

With both n and m and n being non-empty linked list, then,

O/P:

 before join operation :
1->2->3->4->5->null
6->7->8->9->null

 after join operation :
1->2->3->4->5->null
6->7->8->9->1->2->3->4->5->null

With n being empty linked list, then,

O/P:

---

Correct Answer: $B$

Comments

If I write      while(p->next != NULL || P!=NULL);

then it's valid ???

---

typedef struct node { //Structure tag name
int data;
struct node * next;
}node; //typedef identifier

Even though Structure tag name and typedef identifier have same name node, why isn’t this causing a compiler error?

---

@mrinmoyh

Yes it’s valid.

Also note that, while(p->next != NULL || p!=NULL) is equivalent to while(p->next || p)

Answer 2

here it is explicitely mentioned that LL are terminated by NULL

so suppose i have m as 1->2-> NULL

and n= 3->4->NULL

so according to the code fragement we need to append M to list N

but in the process is the lsit N is empty but valid like this

node*head;

head->NULL:

it may dereferrence a NULL pointer
so

i think

B is correct answer here

correct me if i am wrong

Comments

ohh i didnt knew it sir so this year every IIT is going to get involved in paper setting EVEN IISC ?

@Arjun sir

---

Yes. I do not have solid proof for the same but this is what I heard from genuine sources. Also new IIT professors usually do not form part of question setting. If we look at the 2 sets of 2017 or 3 sets each of 2016 and 2015 they hardly have any similarity. So, it must be true.

---

@Arjun sir..

NULL terminated list means the list ends node with next field as NULL

But anyway there is atleast one node ..so how can 'n' points to NULL..it points to node with next field NULL and no element ?

What this means actually 

Answer 3

here WHILE loop in Void Join() takes the pointer P to last node of list N since it was pointing to list N head initially hence once we reach last node p->next=m will append the list M to end of list N as ADDRESS of M's head is saved in the last node of N so correct option should be

OPTION (A)

Comments

thanx..it resolved my doubt.. now only one question i am uneasy is the control flow question. 1-43... :D

---

I ticked B. hope it will be correct ! ..tensed !

---

deka, your view on question 1-43?

Answer 4

It is not mentioned explicitly that the lists are non-null. They are valid null-terminated implies if the list is non-empty the last node pointer successfully points to the null. Thus if the list n is itself NULL then dereferecing will create NULL pointer issue. Thus option B) Either null de-reference issue or appends list should be correct ans.

Comments

“ the list n is itself NULL “, what is the significance of this? How can head of the LL points to NULL.

---

@himanshud2611

"Assuming that m and n point to valid NULL-terminated linked lists" – the line says  that the linked lists are not infinite they are finite ..