Samsung Interview Question
Software Engineer / DevelopersTeam: SEL
Country: India
Interview Type: In-Person
Do we need to move the nodes from existing linked lists to the result list? OR Do we need to create a result list with new nodes with content copied?
Anyway, here is working code. Remove spaces in http word, CareerCup does not allow URLs :(.
h t t p://codepad.org/nn3loNH0
Time Complexity: O(m + n) where m is List1 length and n is List 2 length.
Space Complexity: O(constant) - Nodes from existing lists are moved into result list
Thanks,
Laxmi
Linklist Merge2Lists(Linklist s,Linklist t)
{
Linklist head=NULL,tail=NULL,p1=s,p2=t;
if((s==NULL)&&(t==NULL)) return NULL;
if(s==NULL) return t;
if(t==NULL) return s;
while((p1!=NULL)&&(p2!=NULL))
{
if(p1->data>p2->data)
{
if(head==NULL) head=p2;
if (tail==NULL) tail=p2;
else tail->next=p2;
tail=p2;
p2=p2->next;
if(head==NULL) head=p2;
}
else
{
if(head==NULL) head=p1;
if (tail==NULL) tail=p1;
else tail->next=p1;
tail=p1;
p1=p1->next;
}
}
if(p1!=NULL)
{
tail->next=p1;
}
else
{
tail->next=p2;
}
return head;
}
Sorry for Abbreviation.. Its Time Optimization and Space Optimization .. :)
- hprem991 November 07, 2011