单链表合并为有序链表

《单链表合并为有序链表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1、已知两个链表head1和head2各自有序，请把它们合并成一个链表仍然有序，要求用递归方法实现。#include#includestructNode{intnum;Node*next;};Node*Merge(Node*head1,Node*head2){if(head1==NULL)returnhead2;if(head2==NULL)returnhead1;Node*head=NULL;if(head1->numnum){head=head1;head->next=Merge(head1->next,hea

2、d2);}else{head=head2;head->next=Merge(head1,head2->next);}returnhead;}2、递增有序的2个单链表合并成一个递增有序的单链表，不用任何库函数调用/*题目描述:2个递增有序的单链表，请你把它两个合并成一个有序的单链表，分普通和不能用任何库函数2种方法作者:xiaocui时间:2007.11.4版本:v1.0*//*说明:如果采用一般的做法，直接申请新的空间，组成一个新的单链表，直接进行归并就可以得到整体的有序序列，这个相对比较简单。如果不能用任何库函数，也就是不能利用malloc分配内存，就是要利用现有的2个链

3、表，进行元素交换得到最后有序的链表。*/#includeusingnamespacestd;/*单链表节点*/structnode{intvalue;node*next;};/*给单链表添加节点*/voidinsertNode(node*head,intvalue){node*p=head->next;if(p==NULL){  p=newnode;  p->value=value;  p->next=NULL;  head->next=p;  return;}while(p->next!=NULL){  p=p->next;}node*tmp=newn

4、ode;tmp->value=value;tmp->next=NULL;p->next=tmp;}/*遍历输出链表节点*/voidprint(node*head){node*p=head->next;while(p!=NULL){  cout<value<<"";  p=p->next;}cout<next=NULL;node*p=headA->next;node*q=headB

5、->next;if(p==NULL){  returnheadB;}if(q==NULL){  returnheadA;}while((p!=NULL)&&(q!=NULL)){  if(p->value==q->value)  {   insertNode(head,p->value);   insertNode(head,q->value);   p=p->next;   q=q->next;  }  elseif(p->valuevalue)  {   insertNode(head,p->value);   p=p->next;  }  elseif(p->

6、value>q->value)  {   insertNode(head,q->value);   q=q->next;  }}while(p!=NULL){  insertNode(head,p->value);  p=p->next;}while(q!=NULL){  insertNode(head,q->value);  q=q->next;}returnhead;}/*下面实现不使用任何库函数，利用交换的方法在原空间实现整体有序。方法是先确定哪一个链表的第一个节点的值小，把这个链表的头结点作为合并后链表的头结点，然后比较2个有序链表的当前节点的值，如果代表最后合并链

7、表的值小，则不用交换，否则把两个值交换，最后合并链表始终保持两个值中的小值。另一个链表由于交换了一个元素，当前元素可能影响该链表的有序递增，对其进行调整使其保持递增有序，然后重复上述动作，直到一个链表遍历结束，然后把剩余的链表连接起来就行。*//*调整链表的第一个节点，使其变成递增有序*/voidchg2sort(node*head,node*&p){if(head->next==NULL)//没有节点，直接返回{  return;}node*s=head;while(s->next!=p)//s指向p的前一个节点