Amazon Interview Question
Software Engineer in TestsNeat solution. It takes care of the condition where first list goes out before the second one. The other case is handled automatically.
Modifying the previous code, this code handles all the cases. The trick is to make head2 point to temp2, if temp is null.
So if second list is longer than that's taken care. If first list is longer, then temp will never be null.
Element *Merge2LL(Element **head1, Element **head2)
{
Element *head3 = *head1;
while(*head1 != null && *head2 != null)
{
Element *temp = *head1->next;
Element *temp2 = *head2->next;
*head1->next = *head2;
if(temp != null)
*head2->next = temp;
else
*head2->next = temp2;
*head1 = temp;
*head2 = temp2;
}
return head3;
}
merge(p1,p2){
ptemp=p1->next;
p1->next=p2;
merge(p2,ptemp);
}
I ignore the boundary. add it yourself.
Node* mergeMakeNew(Node *head1,Node *head2)
{
Node *head3,*temp1,*temp2;
int count = 0;
head3 = NULL;
temp1 = head1;
temp2 = head2;
while(temp1 != NULL || temp2 != NULL)
{
if(count % 2 == 0)
{
head3 = insert(head3,temp1->n);
temp1 = temp1->next;
}
else
{
head3 = insert(head3,temp2->n);
temp2 = temp->next;
}
count++;
}
if(temp1 != NULL)
{
while(temp1 != NULL)
{
head3 = insert(head3,temp1->n);
temp1 = temp1->next;
}
}
if(temp2 != NULL)
{
while(temp2 != NULL)
{
head3 = insert(head3,temp2->n);
temp2 = temp2->next;
}
}
return head3;
}
Node* mergeMakeNew(Node *head1,Node *head2)
{
Node *head3,*temp1,*temp2;
int count = 0;
head3 = NULL;
temp1 = head1;
temp2 = head2;
while(temp1 != NULL || temp2 != NULL)
{
if(count % 2 == 0)
{
head3 = insert(head3,temp1->n);
temp1 = temp1->next;
}
else
{
head3 = insert(head3,temp2->n);
temp2 = temp->next;
}
count++;
}
if(temp1 != NULL)
{
while(temp1 != NULL)
{
head3 = insert(head3,temp1->n);
temp1 = temp1->next;
}
}
if(temp2 != NULL)
{
while(temp2 != NULL)
{
head3 = insert(head3,temp2->n);
temp2 = temp2->next;
}
}
return head3;
}
public Node mergelists ( Node head1, Node head2 )
{
Node Temp;
Node Head_mln;
Head_mln = head1;
while ( head2.next != null && head1.next != null )
{
Temp = head2.next;
head2.next = head1.next;
head1.next = head2;
head1 = head2.next;
head2 = Temp;
}
if (head2.next == null)
{
Temp = head1.next;
head1.next = head2;
head2.next = Temp;
}
elseif (head1.next == null)
{
head1.next = head2;
}
return Head_mln;
}
}
- Confused January 13, 2010