合并链表c

1.非递归

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
	struct ListNode*p=list1,*q=list2,*pnext=NULL,*qnext=NULL;
	//长度为0
    if(!list1){return list2;}
    if(!list2){return list1;}

	if(list1->val > list2->val){
		return mergeTwoLists(list2,list1);
	}

	//长度为1
    if(!p->next){
		if(p->val<=q->val){
			p->next=q;
			return p;
		}
    }

	while(p&&p->next&&q){
		//q>p,qval <= p->next->val)){
			//左连接
			pnext=p->next;
			p->next=q;		
			//q右移，q停在>pnext的前一个位置
			qnext=q->next;
			while((qnext)&&(qnext->val <= pnext->val)){
				q=qnext;
				qnext=qnext->next;
			}
			q->next=pnext;	
			if(!qnext){					
				return list1;
			}
			q=qnext;
			p=pnext;
			//p到达链尾
			if(!p->next){
				p->next=q;
				return list1;
			}
		}
		//q>pnext
		else if((q->val > p->next->val)){
			//右移p，直到pnext>q
			pnext=p->next;
			while((pnext)&&(pnext->val < q->val)){
				p=pnext;
				pnext=pnext->next;
			}
			//p到达链尾
			if(!pnext){
				p->next=q;
				return list1;
			}
		}
	}
	return list1;
}

2.递归

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
	if(!list1){return list2;}
	if(!list2){return list1;}
	
	if(list1->val < list2->val){
		list1->next=mergeTwoLists(list1->next,list2);
		return list1;
	}
	else{
		list2->next=mergeTwoLists(list1,list2->next);
		return list2;
	}
}