题解 | #合并两个排序的链表#

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
#include <cmath>
#include <linux/limits.h>
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //典型的二路归并排序 
	  //给他一个头结点，这个结点不保存值
		ListNode* head = new ListNode(-1);
		head->next = nullptr;
		ListNode* ss = head;
		ListNode* p = pHead1;
		ListNode* q = pHead2;
		//排序直到有一个链表排完
	  //这里的时间复杂度依旧是O(MIN(ph1.len,ph2.len)),整个while只遍历最短的长度
		while(p != nullptr && q != nullptr)
		{
			//存放p链表
			if(p->val <= q->val)
			{
				while(p->next != nullptr && p->next->val <= q->val)
				{
					p = p->next;
				}
				ss->next = pHead1;
				ss = p;
				pHead1 = p->next;
				p = p->next;
				ss->next = nullptr;
				
			}
			//存放q链表
			else 
			{
				while(q->next != nullptr && q->next->val < p->val)
				{
					q = q->next;
				}
				ss->next = pHead2;
				ss = q;
				pHead2 = q->next;
				q = q->next;
				ss->next = nullptr;
				
			}
		}
	  //两个if将剩下的不为空的链表添加到ss的后面
		if(p != nullptr)
		{
			ss->next = pHead1;
		}
		if(q != nullptr)
		{
			ss->next = pHead2;
		}
		ss = head->next;
	  //销毁头结点
		delete head;
		return ss;
    }
};