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

"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 ..