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

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // 处理空情形
        if(pHead1 == NULL) return pHead2;
        if(pHead2 == NULL) return pHead1;
        // 新的起始节点
        ListNode* pNewHead;
        if(pHead1->val <= pHead2->val) pNewHead = pHead1;
        else pNewHead = pHead2;
        
        // last_pos用来保存正在移动的指针的上一个节点
        ListNode* last_pos = pHead1;
        // turn=true表示链表1指针在前进，false表示链表2指针在前进
        bool turn = true;
        if(pHead2->val < pHead1->val){
            last_pos = pHead2;
            turn = false;
        }
        /** 
        对于两个链表中正在前进的那一个
            1.如果当前值小于等于另一个链表指针的值，继续前进
                **重点是第一次切换到一条链表时，last_pos和链表当前指针是一样的
                **若连续在一条链表上前进了两次，则需要更新last_pos保证跟当前链表指针相差1
            2.如果当前值大于另一个链表指针值，更改last_pos的next指针，然后切换到另一链表
        **/
        while(pHead1 != NULL && pHead2 != NULL){
            if(turn){
                if(pHead1->val > pHead2->val){
                    last_pos->next = pHead2;
                    last_pos = pHead2;
                    turn = false;
                }
                else {
                    pHead1 = pHead1->next;
                    if(last_pos->next != pHead1) last_pos = last_pos->next;
                }
            }else{
                if(pHead2->val > pHead1->val){
                    last_pos->next = pHead1;
                    last_pos = pHead1;
                    turn = true;
                }
                else {
                    pHead2 = pHead2->next;
                    if(last_pos->next != pHead2) last_pos = last_pos->next;
                }
            }
        }
        // 处理有一条链表已经结束的情况，直接接到另一条后面
        if(pHead1 == NULL) last_pos->next = pHead2;
        if(pHead2 == NULL) last_pos->next = pHead1;
        return pNewHead;
    }