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

/*
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* dPtr = (pHead1->val) < (pHead2->val) ? pHead1 :
                         pHead2; //移动指针,初始化为最小端链头
        ListNode* sPtr = (dPtr == pHead2) ? pHead1 : pHead2; //固定指针
        ListNode* tmp = nullptr;
		//取首元素较小的链表为基本链表(其必定为输出结果),移动指针指向首位,另一链表首位安置固定指针;
		//移动指针逐个与固定指针的指向值比较遍历,保证遍历过的元素满足递增排序,位置固定;
		//当移动指针遇到更大值时,移动指针后续链表与固定指针交换;
		//重复移动指针的比较遍历,直到移动指针行至当前链末,最后合并固定指针指向的链表.
        while (true) {
            while (dPtr->next != nullptr && ((dPtr->next->val) <= (sPtr->val)))
                dPtr = dPtr->next;
            //dPtr->next == nullptr || dPtr->next->val > sPtr->val
            if (dPtr->next == nullptr) {
                dPtr->next = sPtr;
                break;
            }
            tmp = dPtr->next;
            dPtr->next = sPtr;
            sPtr = tmp;
        }
        return ((pHead1->val) < (pHead2->val)) ? pHead1 : pHead2;
    }
};