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

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) 
	{
        if(pHead1==nullptr||pHead2==nullptr)
		{
			return pHead1==nullptr?pHead2:pHead1;
		}
		else 
		{
			ListNode* L1,* L2,* s;
			ListNode* head;
			L1=pHead1;
			L2=pHead2;//双指针


			if(L1->val<L2->val)
			{
				s=L1;
				L1=L1->next;
			}
			else 
			{
				s=L2;
				L2=L2->next;
			}
			head=s;//以小的为起始


			while(L1!=nullptr||L2!=nullptr)//进行连接
			{
				if(L1==nullptr)
				{
					s->next=L2;
					L2=nullptr;
					break;
				}
				else if(L2==nullptr)
				{
					s->next=L1;
					L1=nullptr;
					break;
				}
				else 
				{
					if(L1->val<=L2->val)
					{
						s->next=L1;
						s=s->next;
						L1=L1->next;
					}
					else 
					{
						s->next=L2;
						s=s->next;
						L2=L2->next;
					}
				}

			}


			return head;	
		}
		
    }
};

此代码也适用于不等长链表合并

基本思路是设置游标L1在链表pHead1上移动，设置游标L2在链表pHead2上移动，s在合并链表head(为头）上移动

注意s在移动前必须先连接到除开已在pHead中结点外的最小结点上，当s到nullptr表明head已经连接完毕

如果制定以下规则

1.起始时L1，L2指向各自头结点，

2.当S移动到L1（L2时）L1（L2）向后移动一位，

那么在每次S即将连接下一个结点时，下一个结点必为L1，L2所指结点值较小的一个。