设计两个有序单链表的合并排序算法

Question

如题所述

Answer 1

方法一:依次取链表2的节点,和链表1中的节点比较,找好位置之后插入到链表1中,然后两个链表指针各加一

方法二:另外建一个空链表,然后分别取两个链表的节点,按照顺序,放入空链表中

方法三:两个链表先连接然后排序(效率最低的)

Answer 2

方法二:另外建一个空链表,然后分别取两个链表的节点,按照顺序,放入空链表中
void mergelklist(lklist *ha,lklist *hb,lklist *&hc)
{
lklist *s=hc=0;
while(ha!=0 && hb!=0)
if(ha->data<hb->data){if(s==0) hc=s=ha; else
{s->next=ha; s=ha;};ha=ha->next;}
else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;}
if(ha==0) s->next=hb; else s->next=ha;
}