The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
3.5k views

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.

asked in DS by Boss (7.9k points)
recategorized by | 3.5k views
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 .

7 Answers

+17 votes
Best answer

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:


 

answered by Veteran (57.5k points)
edited by
Could u plz tell me

if option B) will be the answer, then which part of code should be added?

then will the code be like this?

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

 

@srestha, to avoid null dereference, you have to check p using if(p) before using p->next
how? explain

while under if block?write code
void join(node* m, node* n) {
    if(n) {
        node *p = n;
        while(p->next != NULL) {
            p = p->next;
        }
        p->next = m;
    }
}

Note : Writing if(n) achieves the same thing as writing if(n != NULL)

+22 votes
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
answered by Veteran (20.5k points)
edited by
i am confused about this too but this is my idea :

we will never defereference a null pointer ( with the given code ) unless the given list is null !!
and if the given ponter is null it wouldnt be a valid list isnt it ??
@Uddipto "dereference" means access the content of memory location. This won't happen for the case you told. But it happens when n is NULL.
but node * head

head->null is also a valid list
A pointer having a value NULL doesn't refer to any valid object.
In computing, a null pointer has a value reserved for indicating that the pointer does not refer to a valid object. Programs routinely use null pointers to represent conditions such as the end of a list of unknown length or the failure to perform some action; this use of null pointers can be compared to nullable types and to the Nothing value in an option type.
https://en.wikipedia.org/wiki/Null_pointer.

A pointer having a value NULL doesn't refer to any valid object.
In computing, a null pointer has a value reserved for indicating that the pointer does not refer to a valid object. Programs routinely use null pointers to represent conditions such as the end of a list of unknown length or the failure to perform some action; this use of null pointers can be compared to nullable types and to the Nothing value in an option type.
https://en.wikipedia.org/wiki/Null_pointer.

 

@mkg think over this perspective - If we assume null list as invalid and suppose you have a function append () which adds element at end of list the meaning turns out to be "Appending element to an invalid list"  which is not correct isn't it ? then meaning should be "Appending element at end of empty list". Moreover the examiner should have specified explicitly that the lists are non-null.
@mkg I think valid object simply means...refering to object which follow given struct node structure.
@Arjun sir dont u think the question should be like m and n points to heads of the two linked lists then its easy to tick 2 as one of them can be NULL

 ..simply what do they mean by VALID NULL TERMINATED LINKED LISTS where does the list exist when the head is NULL optionA can also be right IIT ROORKEE'S paper setting is not that good even with that set 2 Circular queue question they didnt mention clearly what they meant by it

what should we assume by valid NULL TERMINATED ?? if a pointer is null then how will it be a list and that too a valid one ??
True - that ambiguity is there. By valid null-terminated I guess they meant an implementation where head points to the first node and when there are no elements it points to NULL.

PS: IITR did not make the GATE paper -- they were only involved in conducting the exam and deciding that 0.33 is better for negative mark than 1/3. GATE question paper is made by all IITs AFAIK.
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.
+12 votes
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)
answered by Loyal (2.9k points)
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
can not a valid list empty
is not node*head;

head->null a valid list but empty?
B) looks more appropriate as it handles both null case and non-null case...
problem is created by the word "VALID LIST"
Answer should be B.

I think Valid simply means that given lists are following given struct node Structure.

Thus valid list can be empty.

@Arjun sir see this

http://cslibrary.stanford.edu/105/LinkedListProblems.pdf 

page 14

here it says there may be list like head->Null ,...is not that list valid..

 

@Uddipto Yes, as per logic/convention that should be the answer. Ideally the ambiguity should have been avoided :( I'm taking B as answer - though I'm not sure 100%. This ambiguity is marked in the key.
just tell me one thing.. we can tell an empty linnked list is valid..if it follows convention
yes, it is valid. It just depends on what the question setter had in mind by using the word "valid". But 99.99% key will be B.
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?
+3 votes

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.

answered by Loyal (3.3k points)
+1 vote
Here they clearly mention m and n are null terminate list i.e. some of element are already persent in both list => append list m to the end of list n for all inputs option(A) is correct
answered by (101 points)
empty list are also NULL terminated right ?
0 votes

The correct answer is (A)

Explanation:

1. void join(node *m, node *n){

    Here we are sending pointer reference of two node type data. It is a linked list.

2. node *p = n;

    Now, new pointer node p defined with its initial value equal to n. So now, p also points to start of n.

3. while (p->next !=NULL){

    start of traversal of linked list. If the next pointer of the node is pointing to NULL then stop there.

4. p = p->next;

    If p->next is not pointing to NULL i.e. it is not end of the list then update value of p = p->next i.e. now it will be pointing to the next node.

5. }

   When the loop ends, the p will be pointing to the last node with p->next = NULL

6. p->next = m;

   p->next which was pointing to NULL now will point to m, which the start of next node.

7. }

   End of program.

So, list m will append to end of list n.

answered by (27 points)
great explaination
0 votes
may be possible for null pointer derefrences because m and n may point at end of list. which are null.
answered by (153 points)


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

29,167 questions
36,992 answers
92,226 comments
34,837 users