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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
  
  //思路：通过遍历pHead1的节点，满足插入条件则插入pHead2的结点
  
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // write code here
        if(pHead1 == nullptr && pHead2 == nullptr){
            return nullptr;
        } //如果pHead1 和 pHead2都为空，直接返回空
			//{} + {} = {};
        if (pHead1 == nullptr ) {
            return pHead2;
        } //如果pHead1为空，则直接返回pHead2
	  		//{} + {1, 2, 3} -> {1, 2, 3}
        if (pHead2 == nullptr ) {
            return pHead1;
        } //如果pHead2为空，则直接返回pHead1
        	//{1, 3} + {} = {1, 3}
	  
        ListNode* ptr1 = pHead1;
        ListNode* ptr2 = pHead2;
		//用ptr1指针遍历pHead1指针， 用ptr2指针遍历pHead2指针
	  
        while (ptr1) {
		//循环条件为ptr1不为空
            if (pHead1->val >= pHead2->val) {
               ptr2 = ptr2->next;
               pHead2->next = pHead1;
               pHead1 = pHead2;
               pHead2 = ptr2;
            }	//如果插入位置在头结点之前，插入节点并更新pHead1头结点的位置
			
            if (ptr1->val <= pHead2->val && !ptr1->next) {
                ptr1->next = pHead2;
                return pHead1;
            }	//在pHead1的末尾插入，且ptr1指针的下一个位置为空 
		  		//{6} + {7， 8，9} -> {6, 7, 8, 9} 

            if (ptr1->val <= pHead2->val && pHead2->val <= ptr1->next->val && ptr1->next) {
                ptr2 = ptr2->next;
                pHead2->next = ptr1->next;
                ptr1->next = pHead2;
                pHead2 = ptr2;
            }	//在中间插入节点

            if (pHead2 == nullptr) {
                break;
            }//pHead2 节点全部插入之后直接推出循环
            ptr1 = ptr1->next;
		  //更新ptr1指针
        }
        return pHead1; //返回pHead1
    }
};