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

第三题

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // 归并排序 ans是会一步一步往后走的，所以ret_ans相当于头结点保存下来返回结果
        ListNode *ans=new ListNode(0);
        ListNode *ret_ans=ans;
        // 循环条件
        while(pHead1!=NULL && pHead2!=NULL)
        {
            // 归并排序的关键，看第一个结点谁最小，连接到ans上
            if(pHead1->val < pHead2->val)
            {
                ans->next=pHead1;
                ans=ans->next;
                pHead1=pHead1->next;
            }
            else{
                ans->next=pHead2;
                ans=ans->next;
                pHead2=pHead2->next;
            }
        }
        
        // 上面退出循环是有一个做完了
        // 但是另一个可能还没有做完，所以要把没做完的直接链接到结尾
        if(pHead1 != NULL)
            ans->next=pHead1;
        else
            ans->next=pHead2;
        
        return ret_ans->next;
    }
};