LeetCode 21. 合并两个有序链表（链表）

左手的ㄟ右手 2022-11-28 13:51 172阅读 0赞

**上一篇博客：[LeetCode 20. 有效的括号（栈、字符串）][LeetCode 20.]**

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 21. 合并两个有序链表][LeetCode 21.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  示例
 *  题解
 *   *  解题思路
     *  解题代码
     *  时间复杂度
     *  提交情况

# 题目信息 #

## 题目描述 ##

将两个升序链表合并为一个新的 **升序** 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

## 示例 ##

> 输入：1->2->4, 1->3->4  
> 输出：1->1->2->3->4->4

# 题解 #

## 解题思路 ##

这道题目其实就是经典的 **2路-归并算法**，在`归并排序`算法中我们就使用到了这一算法（详细的解释请看 [经典排序算法之归并排序详解][Link 1]）。

基本思路是当两个链表都不为空时不断的比较两个链表第一个节点值的大小，将较小的节点放到新链表的最后一个节点，然后使指向该链表当前节点的指针指向下一个节点，再继续进行比较。当其中有一个链表遍历完之后，我们直接将另外一个链表剩余的节点依次接到新链表的后面即可。

首先我们定义一个虚拟头结点 `dummy` ，然后定义一个变量 `tail` 来指向虚拟头结点的尾结点。然后遍历两个链表，当两个链表都不为空的时候，我们比较两个链表的第一个节点的大小，将较小值的节点放到新链表的最后一个节点。再更新新链表的尾结点，使 `tail` 指向较小值的节点。不断的进行比较添加，最后返回虚拟头结点的下一个节点即可。

![图解1][1]  
![图解2][2]  
![图解3][3]  
![图解4][4]  
![图解5][5]

## 解题代码 ##

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
    class Solution { 
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 
            auto dummy = new ListNode(-1), tail = dummy;
            while (l1 && l2) { 
                if (l1->val < l2->val) { 
                    tail->next = l1;
                    tail = tail->next;
                    l1 = l1->next;
                } else { 
                    tail->next = l2;
                    tail = tail->next;
                    l2 = l2->next;
                }
            }
            
            if (l1) tail->next = l1;
            if (l2) tail->next = l2;
            return dummy->next;
        }
    };

## 时间复杂度 ##

假设 **l1** 的长度为 **n**， **l2** 的长度为 **m**，则时间复杂度为 **O(m + n)**。

## 提交情况 ##

![提交情况][20200818123025635.png]

--------------------

> 未完待续，持续更新中……  
> ![Tomcat 我们走][Tomcat]

[LeetCode 20.]: https://blog.csdn.net/qq_41575507/article/details/108053406
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode 21.]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[Link 1]: https://blog.csdn.net/qq_41575507/article/details/107300891
[1]: /images/20221124/d45864b1200e412bbde2bb44ff4999f8.png
[2]: /images/20221124/0ab2a83464a840a7be54f70eb7d7a40e.png
[3]: /images/20221124/ae0b9fd7dd9346b494185190629c5129.png
[4]: /images/20221124/80e5721fe0e14bdbae8f48546eaed90b.png
[5]: /images/20221124/7c43b6251134418689cd3b0e290449e8.png
[20200818123025635.png]: /images/20221124/527bd04c15da4faf86b0a084938f6fd9.png
[Tomcat]: /images/20221124/4a67f33806a34432a08d15c187747289.png