//2_15
/*
问题描述:
已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n。
试写一个算法将这两个链表链接在一起,假设指针hc指向链接后的链表的头结点,并
要求算法以尽可能短的时间完成链接运算。试分析你的算法的时间复杂度。
*/
//完成日期:2005/3/6 (未经测试)
//作者:杨明哲
//传入两个链表的指针的长度
//传出链接后的链表的指针
//时间复杂度为O(t),t为m,n中的较小者
ElemType* merge(ElemType* ha,unsigned m,ElemType* hb,unsigned n)
{
ElemType* htemp,*hc;
if(m>n)
{
htemp=hc=hb;
while(htemp->next!=NULL)
{
htemp=htemp->next;
}
htemp->next=ha;
}
else
{
htemp=hc=ha;
while(htemp->next!=NULL)
{
htemp=htemp->next;
}
htemp->next=hb;
}
return hc;
}
评论