【题解】合并两个排序的链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【题解】合并两个排序的链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接：合并两个排序的链表
解题思路1：迭代

创建一个新的单链表，对两个链表进行迭代，每次取较小元素放入新链表中，直至某一个链表为空，则结束循环，接着判断是否有某个链表没有遍历结束，再将未遍历结束的链表部分放入结果链表中。
一般创建单链表，都会设一个虚拟头结点，也叫哨兵，因为这样每一个节点都有一个前驱节点，完美解决了各种判空逻辑的烦恼，所有的节点将被统一处理。

代码如下：文章来源地址https://www.toymoban.com/news/detail-619088.html

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* vhead = new ListNode(-1);
        ListNode* cur = vhead;
        while(pHead1!=nullptr && pHead2!=nullptr){
            if(pHead1->val <= pHead2->val){
                cur->next = pHead1;
                pHead1 = pHead1->next;
            }else{
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }
        cur->next = pHead1 ? pHead1 : pHead2;
        return vhead->next;
    }

解题思路2：递归
本题进行迭代求解十分方便，此处还是提供递归的解法，增强递归的理解。

首先，结束递归的条件：某一个链表为空，则返回非空链表，递归结束
其次：当前递归条件，若pHead1->val < =pHead2->val，将较小的pHead1->next与后面merge的头连接，即pHead1->next = Merge(pHead1->next, pHead2)，较大时同理
递归的返回值：排好序的链表头

代码如下：

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1 == nullptr) return pHead2;
        if(pHead2 == nullptr) return pHead1;
        if(pHead1->val <= pHead2->val){
            pHead1->next = Merge(pHead1->next, pHead2);
            return pHead1;
        }else{
            pHead2->next = Merge(pHead1, pHead2->next);
            return pHead2;
        }