## Microsoft Citrix System Inc Interview Question

Software Engineer / Developers Software Engineer in Testst = linklist of one sorted list

u = linklist of other sorted list.

r = result link list

for ( t++ and u++)

{if t.data < u.data

r->next = t

r = r->next

if t.data = u.data

r->next = t

r= r->next

if t.data >u.data

r->next = u

r= r->next

}

if any one linklist become empty , put other linklist into result as such.

t = linklist of one sorted list

u = linklist of other sorted list.

r = result link list

for ( t++ and u++)

{if t.data < u.data

r->next = t

r = r->next

if t.data = u.data

r->next = t

r= r->next

if t.data >u.data

r->next = u

r= r->next

}

if any one linklist become empty , put other linklist into result as such.

node *merge(node *p,node *q)

{

if(p==NULL) return q;

if(q==NULL) return p;

if(p->data==q->data)

{

p->next=merge(p->next,q->next);

delete q;

return p;

}

if(p->data>q->data)

{

q->next=merge(p,q->next);

return q;

}

p->next=merge(p->next,q);

return p;

}

Have you read the Q carefully? It requires us to remove the duplicates also. Your code doesn't (ex. it fails when p={1} & q={1,1}) remove the duplicates. And for god's sake please read the Q carefully before posting codes. You are spamming the forums in this way.

thanks

I think his code is correct and it does handle duplicates. Maybe you should read the code carefully before commenting.

Sushant: that code doesn't handle 1,1. I tried it:

```
#include "stdafx.h"
#include <iostream>
using namespace std;
struct node
{
int data;
node * next;
};
node *merge(node *p,node *q)
{
if(p==NULL) return q;
if(q==NULL) return p;
if(p->data==q->data)
{
p->next=merge(p->next,q->next);
delete q;
return p;
}
if(p->data>q->data)
{
q->next=merge(p,q->next);
return q;
}
p->next=merge(p->next,q);
return p;
}
int main ()
{
node *a = new node(); a->data = 1; a->next = NULL;
node *b = new node(); b->data = 1; b->next = new node(); b->next->data = 1; b->next->next = NULL;
node *x = merge(a,b);
while(x != NULL)
{
cout<<x->data<<"->";
x = x->next;
}
cout<<endl;
return 0;
}
```

=> output:

1->1

```
Node *merge(Node *h1, Node *h2)
{
Node *head = NULL, *prev = NULL, *curr = NULL;
Node *c1 = h1, *c2 = h2;
while (c1 || c2) {
if (c2 == NULL) {
curr = c1;
c1 = c1->next;
} else if (c1 == NULL) {
curr = c2;
c2 = c2->next;
} else if (c1->value <= c2->value) {
curr = c1;
c1 = c1->next;
} else {
curr = c2;
c2 = c2->next;
}
if (prev) {
if (prev->value == curr->value)
continue;
else
prev->next = curr;
}
if (head == NULL)
head = curr;
prev = curr;
}
return head;
}
```

```
Node lastNodeAdded = NULL;
list toReturn;
while(!list1.empty() || !list2.empty())
{
lastlastNode = lastNodeAdded;
if(list1 != NULL && lastNodeAdded.getValue == list1.getValue()
while(list1 != NULL && list1.getValue() == lastNodeAdded)
list1 = list1.getNext();
if(list1 != NULL && lastNodeAdded.getValue == list2.getValue()
while(list2 != NULL && list2.getValue() == lastNodeAdded)
list2 = list2.getNext();
if(list1 != NULL && list2 != NULL)
{
if(list1.getValue() > list2.getValue())
{
lastNodeAdded = list2.getValue();
list2 = list2.getNext();
}
else
{
lastNodeAdded = list1.getValue();
list1 = list1.getNext();
}
}
else if(list1 != NULL && list2 == NULL)
{
lastNodeAdded = list1;
list1 = list1.next();
}
else if(list1 == NULL && list2 != NULL)
{
lastNodeAdded = list2;
list2 = list2.next();
}
else
{
continue;
}
lastlastNode.setNext(lastNodeAdded);
toReturn.add(lastNodeAdded);
}
```

Time O(N+M), Space O(N+M) the list we return. I wrote the code on notepad, there maybe some minor issue with the function

pseudo code is as follows:

int mergeList(struct node* list1 , struct node* list2)

{

if (list1 and list2 are null) return failure;

else if (one list of the two list is null) return success;

else

{

while (list1) get the max_number;

while (list2->data <= max_number) get the last pointer in list2 say prev

while (prev is not NULL meaning end of second list)

create new node* add that to last element of list1 and increase both of the list element

}

return success

}

1. Take each node from second list and keep it in the first list by just modifying the pointers - O(n^2) time, no space required

2. Just append the second list to the last node of the first list and do a comparison sort to modify the values within each node - O(nlogn) time, no space

3. Extra list and go over each list linearly to move node the new list - O(list1.length + list2.length) time and same space complexity as well

```
List<int> RemoveDuplicatesAndMerge(int[] A, int[] B)
{
return new List<int>(RemoveDuplicatesAndMergeInternal(A, B));
}
IEnumerable<int> RemoveDuplicatesAndMergeInternal(int[] A, int[] B)
{
int a = 0;
int b = 0;
int last;
while ((a < A.length) && (b < B.Length))
{
if (A[a] < B[b])
{
if (A[a] != last)
{
last = A[a];
yield return A[a];
}
a++;
}
else if (B[b] < A[a])
{
if (B[b] != last)
{
last = B[b];
yield return B[b];
}
b++;
}
else // A[a] == B[b]
{
a++;
b++;
}
}
for (;a < A.length;a++)
{
if (last != A[a])
{
yield return A[a];
}
}
for (;b < B.length;b++)
{
if (last != B[b])
{
yield return B[b];
}
}
}
```

Rectifying UM's solution:

#include "stdio.h"

#include <iostream>

using namespace std;

struct node

{

int data;

node * next;

};

node *merge(node *p,node *q)

{

if(p!=NULL){

while(p->next != NULL && (p->data==p->next->data)){

p=p->next;

}

}

if(q!=NULL){

while(q->next != NULL && (q->data==q->next->data)){

q=q->next;

}

}

if(p==NULL) {

// q=sort(q);

return q;

}

if(q==NULL) {

//p=sort(p);

return p;

}

if(p->data==q->data){

p->next=merge(p->next,q->next);

delete q;

return p;

}

if(p->data>q->data)

{

q->next=merge(p,q->next);

return q;

}

p->next=merge(p->next,q);

return p;

}

int main ()

{

node *a = new node(); a->data = 1; a->next = NULL;

node *b = new node(); b->data = 1; b->next = NULL;

node *x = merge(a,b);

while(x != NULL)

{

cout<<x->data<<"->";

x = x->next;

}

cout<<endl;

return 0;

}

//h1 = head of first link list

//h2 = head of second link list

LIST *merge_linklist(LIST *h1, LIST* h2){

LIST* h3 == NULL; // head of the merged list

LIST *trav,*node; //temporary pointer

if(h1==NULL && h2==NULL)

return NULL;//return NULL if both list are empty

if(h1==NULL)

return h2;

else if(h2==NULL)

return h1

while (h1!=NULL && h2!=NULL) {

//check in the next element is same

//as the previos one

if (h1->value = h1->next->value) {

h1=h1->next;

continue; //ignore the element

}else if (h2->value = h2->next->value) {

h2=h2->next;

continue; //ignore the element

}

if(h1->value < h2->value){

//create a node for final merge list

if(h3 == NULL){

h3 = (LIST*) malloc(sizeof(LIST));

h3->value = h1->value // store the smaller of h1 and h2 into h3

h3->next = NULL;

trav = h3;

}else{

node = (LIST*) malloc(sizeof(LIST));

node->value = h1->value;

trav->next = node;

trav = trav->next;

node->next = NULL;

}

h1= h1->next;

}else if(h1->value > h2->value){

if(h3 == NULL){

h3 = (LIST*) malloc(sizeof(LIST));

h3->value = h2->value // store the smaller of h1 and h2 into h3

h3->next = NULL;

trav = h3;

}else{

node = (LIST*) malloc(sizeof(LIST));

node->value = h2->value;

trav->next = node;

trav = trav->next;

node->next = NULL;

}

h2=h2->next; //move the pointer of the list having the smaller value

}else{// when h1 and h2 are equal

if(h3 == NULL){

h3 = (LIST*) malloc(sizeof(LIST));

h3->value = h2->value // store the smaller of h1 and h2 into h3

h3->next = NULL;

trav = h3;

}else{

node = (LIST*) malloc(sizeof(LIST));

node->value = h1->value;

trav->next = node;

trav = trav->next;

node->next = NULL;

}

h1=h1->next;

h2=h2->next;

}

}//while loop ends

//trav points to tail of the merged list h3

//now we need to attach the tail of h3 to the left over element of the longer list

(h1==NULL) ? (trav->next=h2->next):(trav->next=h1->next);

return h3; // return the head of the merged list

}

```
//h1 = head of first link list
//h2 = head of second link list
LIST *merge_linklist(LIST *h1, LIST* h2){
LIST* h3 == NULL; // head of the merged list
LIST *trav,*node; //temporary pointer
if(h1==NULL && h2==NULL)
return NULL;//return NULL if both list are empty
if(h1==NULL)
return h2;
else if(h2==NULL)
return h1
while (h1!=NULL && h2!=NULL) {
//check in the next element is same
//as the previos one
if (h1->value = h1->next->value) {
h1=h1->next;
continue; //ignore the element
}else if (h2->value = h2->next->value) {
h2=h2->next;
continue; //ignore the element
}
if(h1->value < h2->value){
//create a node for final merge list
if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h1->value // store the smaller of h1 and h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h1->value;
trav->next = node;
trav = trav->next;
node->next = NULL;
}
h1= h1->next;
}else if(h1->value > h2->value){
if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h2->value // store the smaller of h1 and h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h2->value;
trav->next = node;
trav = trav->next;
node->next = NULL;
}
h2=h2->next; //move the pointer of the list having the smaller value
}else{// when h1 and h2 are equal
if(h3 == NULL){
h3 = (LIST*) malloc(sizeof(LIST));
h3->value = h2->value // store the either h1 or h2 into h3
h3->next = NULL;
trav = h3;
}else{
node = (LIST*) malloc(sizeof(LIST));
node->value = h1->value;
trav->next = node;
trav = trav->next;
node->next = NULL;
}
h1=h1->next;
h2=h2->next;
}
}//while loop ends
//trav points to tail of the merged list h3
//now we need to attach the tail of h3 to the left over element of the longer list
(h1==NULL) ? (trav->next=h2->next):(trav->next=h1->next);
return h3; // return the head of the merged list
}
```

public class MergeList {

public Node merge(Node n1,Node n2){

Node current1=n1;

Node current2=n2;

Node start;

if(current1.data>= current2.data){

start = new Node(n1.data);

current1= current1.next;

while(current1!=null){

if(current1.data==n1.data){

current1= current1.next;

}

}

while(current2!=null&& current2.data==n1.data){

current2= current2.next;

}

start.next= merge(current1,current2);

}

else{

start = new Node(current2.data);

current2= current2.next;

while(current2!=null){

if(current2.data==n2.data){

current2= current2.next;

}

}

while(current1!=null&& current1.data==n2.data){

current1= current1.next;

}

start.next= merge(current1,current2);

}

return start;

}

}

package linkedList;

public class MergeList {

public Node merge(Node n1,Node n2){

Node current1=n1;

Node current2=n2;

Node start;

if(current1.data>= current2.data){

start = new Node(n1.data);

current1= current1.next;

while(current1!=null){

if(current1.data==n1.data){

current1= current1.next;

}

}

while(current2!=null&& current2.data==n1.data){

current2= current2.next;

}

start.next= merge(current1,current2);

}

else{

start = new Node(current2.data);

current2= current2.next;

while(current2!=null){

if(current2.data==n2.data){

current2= current2.next;

}

}

while(current1!=null&& current1.data==n2.data){

current1= current1.next;

}

start.next= merge(current1,current2);

}

return start;

}

}

- monika.agarwal712 January 24, 2013