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

/*
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)
		{
			return pHead2;
		}

		if(pHead2 == nullptr)
		{
			return pHead1;
		}

		ListNode* head = new ListNode(pHead1->val);
		ListNode* pnow = head;

		while(pHead1 && pHead2)
		{   // pnow->[pHead1->val]<-head  //假如
			// pHead1->[1]->[3]->[5]
			// pHead2->[2]->[4]->[6]->[8]
			

            //如果1小于等于2 将pnow指向1 1指向下一个位置再于2比较一下
			if(pHead1->val <= pHead2->val )
			{
				pnow->next = pHead1;
			// pnow->[pHead1->val]<-head  //假如
			//          |
			//          v
			// pHead1->[1]->[3]->[5]
			// pHead2->[2]->[4]->[6]->[8]
				pHead1 = pHead1->next;
            // pnow->[pHead1->val]<-head //假如
			//          |
			//          v
			//         [1]->[3]->[5]
			//			     ^
			//               |
			//             pHead1
			// pHead2->[2]->[4]->[6]->[8]
			}
			//如果2小于1 将pnow指向2位置 2指向下一个位置再与1比较一下
			else
			{
				pnow->next = pHead2;
		    //	[pHead1->val]<-head  //假如
			//         |
			//         v
			//        [1]->[3]->[5]
			//		   |    ^
			//         |    | 
			//         v    pHead1
		    //pHead2->[2]->[4]->[6]->[8]
			//          	
				pHead2 = pHead2->next;
			//		[pHead1->val]<-head  //假如
			//          |
			//          v
			//         [1]->[3]->[5]
			//		 pnow    ^
			//        |      |
			//        v    pHead1
		    //        [2]->[4]->[6]->[8]
			//              ^
			//			    |
			//			  pHead2
			}
			//pnow指向下一个位置
			pnow = pnow->next;
		    //		[pHead1->val]<-head  //假如
			//          |
			//          v
			//  pnow-> [1]->[3]->[5]
			//			     ^
			//               |
			//             pHead1
			// pHead2->[2]->[4]->[6]->[8]			

		}
		//当存在有不空链表表示较大，直接连上
         if(pHead1)
		 {
			pnow->next = pHead1;
		 }
		 else 
		 {
		    pnow->next = pHead2;
		 }

		 //刚开始有一个初始化的节点,记得去了
         return head->next;

    }
};