[数据结构与算法]有序单链表的归并多种思路

方法一：?

//方法一： 创建第三个表 
void Merge(LinkList *L1,Linklist *L2,Linklist *&L3){
	LinkList *p=L1->next,*q=L2->next;*r,*s;
	L3=(LinkList *)malloc(sizeof(LinkList));
	//只要用尾插法的时候，一定要增加一个尾指针指向尾节点 
	r=L3;
	while(q!=NULL&&p!=NULL){
		if(p->data<q->data){ //如果l1中的值比l2中的值小 
			s=(LinkList *)malloc(sizeof(LinkList));  //开辟一个新的节点 
			s->data=p->data;    //将该值赋给s 
			p=p->next;    //l1中的p指针后移 
			r->next=s;   
			r=s;   //r指针也后移 
		}else{
			s=(LinkList *)malloc(sizeof(LinkList));
			s->data=q->data;
			q=q->next;
			r->next=s;
			r=s;
	    }
	}
	if(q!=NULL)   p=q;
	while(p!=NULL){  //将未遍历的表的余下节点复制到L3中 
		s=(LinkList *)malloc(sizeof(LinkList));
		s->data=p->data;
		p=p->next;
		r->next=s;
		r=s;
	}
	r->next=NULL;
}

?该方法没有破坏原有的L1L2节点，时间复杂度和空间复杂度均为O(m+n)

注意，L1和L2的头指针不需要发生变化，所以不用引用符号&

方法二：

//方法二：破坏原有单链表
 void merge(LinkList L1,LinkList L2,LinkList &L3){
 	LinkList *p=L1->next,*q=L2->next,*r;
 	L3=L1;   //任选一个链表的头指针作为新表L3的头指针(这里选l1)
 	L3->next=NULL;  //此时l3是空表 
	free(L2);  //此时l2的头指针已无用，释放掉
	r=L3;   //r指向l3的尾节点 
	while(p!=NULL&&q!=NULL){
		if(p->data<q->data){
			r->next=p;
		    p=p->next;  //p指针后移 
		    r=r->next;  //r指针后移 
		}else{
			r->next=q;
			q=q->next;
			r=r->next;
		}
	}
	//将未遍历的表的余下节点链到l3中 
	if(p!=NULL) r->next=p;  
	if(q!=NULL) r->next=q;
 }

空间复杂度O(1),大大减小了内存空间，但必须破坏原有的L1和L2单链表，由这两个单链表的节点重组产生L3.

方法三：

//方法三：递归
void merge(LinkList L1,LinkList L2){
	LinkList *p=L1->next,*q=L2->next;
	while(p!=NULL&&q!=Null){
		if(p->data<q->data){
			p->next=merge(p->next,L2);
			return L1;
		}else{
			q->next=merge(q->next,L1);
			return L2;
		}
	}
} 

补充：

//降序归并（头插法） 
 void merge(LinkList L1,LinkList L2,LinkList &L3){
 	LinkList *p=L1->next,*q=L2->next,*s
 	L3=L1;
 	L3->next=NULL;
 	free(L2);
 	while(p!=NULL&&q!=NULL){
 		if(p->data<q->data){
 			s=(LinkList *)malloc(sizeof(LinkList));  //创建新节点 
 			s->data=p->data;  //用s指针取下p插到l3的头部 
 			p=p->next;     
 			s->next=L->next;  //插入 
 			L->next=s;	
		 }else{
		 	s=(LinkList *)malloc(sizeof(LinkList));
		 	s->data=q->data;
		 	q=q->next;
		 	s->next=L->next;
		 	L->next=s;	
		 }
	 }
	//将未遍历的表的余下节点链到l3中 
	if(p!=NULL) r->next=p;  
	if(q!=NULL) r->next=q;
 }