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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* head = new ListNode(-1);
        ListNode* list = head;
        //这样子更改phead也会改变头结点
        ListNode* pheadx = pHead1;
        ListNode* pheady = pHead2;
        cout << pheadx << '\t' << pHead1 << endl;
        cout << pheady << '\t' << pHead2 << endl;
		// 检查特殊情况
		if (pheadx==nullptr&&pheady==nullptr) {
			return nullptr;
		}
		if (pheadx==nullptr) {
			return pheady;
		}
		if (pheady==nullptr) {
			return pheadx;
		}
		// 开始循环判断
        while (pheadx != nullptr || pheady != nullptr) {
			// 如果碰到phead任何一方为nullptr，则进入以下决策环节
            if (pheadx == nullptr || pheady == nullptr) {
                if (pheadx == nullptr && pheady == nullptr) {
                    return head->next;
                }
                if (pheadx == nullptr) {
                    list->next = pheady;
                    return head->next;
                }
                if (pheady == nullptr) {
                    list->next = pheadx;
                    return head->next;
                }
            }
			// 这里忘记判断了=的情况了，导致用例过一半，超时报错
			// 如果用例过一半左右，有超时报错的话，就考虑是否在循环中有自己没有考虑到的情况！
            if (pheadx->val <= pheady->val && pheady != nullptr &&
                    pheadx != nullptr) {
                ListNode* pnextx = pheadx->next;
                // pheadx->next = nullptr;
				// pheadx和pHead1都是指向同一块内存，不能对任何一方进行破坏链表的操作，否则无法继续下面的循环
				// 不过在这道题中，pheadx指向nullptr都无所谓，这是因为只用一次，并且我已经用pnextx存储了pheadx下一个结点的信息
                list->next = pheadx;
                list = list->next;
                pheadx = pnextx;
                continue;
            }
            if (pheadx->val > pheady->val && pheady != nullptr &&
                    pheadx != nullptr) {
                ListNode* pnexty = pheady->next;
                pheady->next=nullptr;
                list->next = pheady;
                list = list->next;
                pheady = pnexty;
                continue;
            }
        }
        return head->next;
    }
};