Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
The modified code would be
List merge(List head1, List head2) {
if(head1 == null && head2 != null)
return head2;
if(head1 != null && head2 == null)
return head1;
List result = null;
if (head1.data < head2.data) {
result = head1;
result.next = merge(head1.next,head2);
}
else {
result = head2;
result.next = merge(head1,head2.next);
}
return result;
}
private static LinkedList MergeLinkedLists(LinkedList p1, LinkedList p2)
{
LinkedList newHead = new LinkedList();
if (p1 == null && p2 == null) return null;
if (p1 != null && p2 == null) return p1;
if (p1 == null && p2 != null) return p2;
Node Head1 = p1.Head;
Node Head2 = p2.Head;
while (Head1 != null && Head2 != null)
{
if (Head1.Data < Head2.Data)
{
newHead.Add(Head1);
Head1 = Head1.Next;
}
else if (Head1.Data == Head2.Data)
{
newHead.Add(Head1);
Head1 = Head1.Next;
newHead.Add(Head2);
Head2 = Head2.Next;
}
else
{
newHead.Add(Head2);
Head2 = Head2.Next;
}
}
if (Head1 != null)
{
newHead.Current.Next = Head1;
}
if (Head2 != null)
{
newHead.Current.Next = Head2;
}
return newHead;
}
public static void TestMergeLinkedLists()
{
LinkedList p1 = new LinkedList();
LinkedList p2 = new LinkedList();
p1.Add(new Node(3));
p1.Add(new Node(4));
p2.Add(new Node(1));
p2.Add(new Node(1));
p2.Add(new Node(1));
p2.Add(new Node(7));
Console.Write("List1 = ");
p1.Print();
Console.Write("List2 = ");
p2.Print();
Console.WriteLine("---------------------------");
LinkedList lst = MergeLinkedLists(p1,p2);
lst.Print();
}
public class LinkedList
{
private Node _Head;
private Node _Current;
public Node Head
{
get
{
return _Head;
}
set
{
_Head = value;
}
}
public Node Current
{
get
{
return _Current;
}
set
{
_Current = value;
}
}
public LinkedList(Node pH)
{
_Head = pH;
_Current = _Head;
}
public LinkedList()
{
_Head = null;
_Current = null;
}
public void Add(Node pD)
{
if (pD == null) return;
if (_Current != null)
{
_Current.Next = pD;
_Current = _Current.Next;
}
else
{
_Head = pD;
_Current = _Head;
}
}
public void Print()
{
Node pH = _Head;
while (pH != null)
{
if (pH.Next != null)
Console.Write(pH.Data.ToString() + "->");
else
Console.Write(pH.Data.ToString());
pH = pH.Next;
}
Console.WriteLine("");
}
}
Output:
List1 = 3->4
List2 = 1->1->1->7
---------------------------
1->1->1->3->4->7
node* merge(node* & p1,node* & p2)
{
if(p1==NULL)
return p2;
if(p2==NULL)
return p1;
node* temp;
if(p1->val>p2->val)
{
temp=p1;
p1=p2;
p2=temp;
}
temp=NULL;
node* temp1 = p1;
while(p1!=NULL && p2!=NULL)
{
while(p1->val<=p2->val)
{
temp=p1; // store the previous node;
if(p1->next==NULL)
{
p1->next=p2;
return temp1;
}
p1=p1->next;
}
temp->next=p2;// insert the node in first list
while(p2->next!=NULL&&p2->next->val<p1->val)
p2=p2->next;
temp=p2->next;
p2->next=p1;
p2=temp;
}
return temp1;
}
node* merge(node* & p1,node* & p2)
{
if(p1==NULL)
return p2;
if(p2==NULL)
return p1;
node* temp;
if(p1->val>p2->val)
{
temp=p1;
p1=p2;
p2=temp;
}
temp=NULL;
node* temp1 = p1;
while(p1!=NULL && p2!=NULL)
{
while(p1->val<=p2->val)
{
temp=p1; // store the previous node;
if(p1->next==NULL)
{
p1->next=p2;
return temp1;
}
p1=p1->next;
}
temp->next=p2;// insert the node in first list
while(p2->next!=NULL&&p2->next->val<p1->val)
p2=p2->next;
temp=p2->next;
p2->next=p1;
p2=temp;
}
return temp1;
}
node* merge(node* la, node* lb)
{
// either one is empty return other
if(!la)
return lb;
else if (!lb)
return la;
node *head;
if(la->d < lb->d) {
head = la;
la = la->next;
} else {
head = lb;
lb = lb->next;
}
node *p = head;
while(la && lb) {
if(la->d < lb->d) {
p->next = la;
p = la;
la = la->next;
} else {
p->next = lb;
p = lb;
lb = lb->next;
}
}
if(la)
p->next = la;
else
p->next = lb;
return head;
}
Take a new pointer say merged_pointer and point it to the lesser of the two start pointer , next keep on comparing the two linked list and keep on connecting the lesser to the merged_pointer. Whichever pointer was less that pointer will be moved to the next position. Keep on doing this until the end of one of the linked list is reached and then point the merged_pointer to the rest of the other linked list. This is very similar to the merge algorithm.
struct list{
int value;
struct listt *next;
}*temp,*p1,*p2,*final,*first_final;
struct list * merge(struct list *a,struct list *b)
{
if(a==NULL && b==NULL)
return NULL;
else if(a==NULL)
return b;
else if(b==NULL)
return a;
first_final=NULL;
if(a->value>b->value)
{
first_final=b;
b=b->next;
first_final->next=NULL;
temp=first_final;
}
else
{
first_final=a;
a=a->next;
first_final->next=NULL;
temp=first_final;
}
while(a!=NULL && b!=NULL)
{
//printf("Compared\n");
if(a->value>b->value)
{
temp->next=b;
temp=temp->next;
b=b->next;
temp->next=NULL;
}
else
{
temp->next=a;
temp=temp->next;
a=a->next;
temp->next=NULL;
}
}
if(a==NULL)
{
temp->next=b;
}
else if(b==NULL)
{
temp->next=a;
}
return first_final;
}
struct list{
int value;
struct listt *next;
}*temp,*p1,*p2,*final,*first_final;
struct list * merge(struct list *a,struct list *b)
{
if(a==NULL && b==NULL)
return NULL;
else if(a==NULL)
return b;
else if(b==NULL)
return a;
first_final=NULL;
if(a->value>b->value)
{
first_final=b;
b=b->next;
first_final->next=NULL;
temp=first_final;
}
else
{
first_final=a;
a=a->next;
first_final->next=NULL;
temp=first_final;
}
while(a!=NULL && b!=NULL)
{
//printf("Compared\n");
if(a->value>b->value)
{
temp->next=b;
temp=temp->next;
b=b->next;
temp->next=NULL;
}
else
{
temp->next=a;
temp=temp->next;
a=a->next;
temp->next=NULL;
}
}
if(a==NULL)
{
temp->next=b;
}
else if(b==NULL)
{
temp->next=a;
}
return first_final;
}
void merge(struct node *head1,struct node *head2)
{
struct node *result=NULL;
while(head1!=NULL && head2!=NULL)
{
if(head1->val < head2->val)
{
result = addnode(result,head1->val);
head1=head1->next;
}
else
{
result = addnode(result,head2->val);
head2=head2->next;
}
}
if(head1==NULL)
{
while(head2!=NULL)
{
result = addnode(result,head2->val);
head2=head2->next;
}
}
else
{
while(head1!=NULL)
{
result = addnode(result,head1->val);
head1=head1->next;
}
}
printlist(result);
printf("\n");
}
This is similar to merge function of mergesort where we copy data into a new array while traversing both arrays. It is mentioned in the question not to copy data but to only manipulate the pointers.
sorry my bad...following code changes the pointers without copying the data
void merge(struct node *head1,struct node *head2)
{
struct node *start=head1;
struct node *prev=(struct node *) malloc(sizeof(struct node));
prev=NULL;
struct node *temp=(struct node *) malloc(sizeof(struct node));
while(head1!=NULL && head2!=NULL)
{
if(head1->val>head2->val)
{
if(prev==NULL)
{
temp=head1;
head1=head2;
start=head1;
head2=head2->next;
head1->next=temp;
}
else
{
prev->next=head2;
temp=head2->next;
head2->next=head1;
head2=temp;
prev=prev->next;
}
}
else
{
prev=head1;
head1=head1->next;
}
}
if(head1==NULL)
prev->next=head2;
printlist(start);
printf("\n");
}
- arsragavan March 05, 2014