一、问题:合并两个有序单链表,合并后的单链表依然有序。

二、分析:

1.有如下两个有序链表str1和str2

2.合并后的新链表的头结点定义为newpHead,采用摘结点法:

三、代码实现(c语言)

sListNode*MergeList(sListNode*FirpHead,sListNode*SecpHead){if(FirpHead==NULL){returnSecpHead;}if(SecpHead==NULL){returnFirpHead;}sListNode*newpHead=NULL;sListNode*firCur=FirpHead,*secCur=SecpHead;sListNode*tail=NULL;if(firCur->data<secCur->data){newpHead=firCur;firCur=firCur->next;}else{newpHead=secCur;secCur=secCur->next;}tail=newpHead;while(firCur!=NULL&&secCur!=NULL){if(firCur->data<secCur->data){tail->next=firCur;firCur=firCur->next;}else{tail->next=secCur;secCur=secCur->next;}tail=tail->next;}if(firCur==NULL){tail->next=secCur;}if(secCur==NULL){tail->next=firCur;}returnnewpHead;