链表是有序的，如何快速合并呢？

曾经终败给现在 2022-09-08 00:28 157阅读 0赞

## 前言 ##

大家好，今天分享 来自于**华为**的**程序员小熊**给大家带来一道**链表**相关的题目，这道题同时也是字节、腾讯、亚马逊和微软等大厂的面试题，即力扣上的第21题-合并两个有序链表。

本文主要介绍**递归**和**迭代**两种策略来解答此题，供大家参考，希望对大家有所帮助。

## 合并两个有序链表 ##

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

![62914de4f42ad74278440822aa56496e.png][] 示例1 ![d81c33342d7a45837a25674c35d9d8d4.png][] 示例及提示

## 解题思路 ##

要想将两个**升序**链表合并成一个新的**升序**链表，比较容易想到通过**递归**去实现。

## 方法一：递归 ##

采用递归的**主要思路**

假设链表分别为 A 和 B，先比较 A 和 B 的头节点的值的大小，选择头节点值较小者（假设为 A）作为新的链表的头节点；然后再比较 A 的第二个节点的值与 B 的头节点的值的大小关系，选择较小者作为新链表的第二个节点；依次类推找出新链表的第三个节点...

> ❝
> 
> 递归终止条件：两链表一个为空时，结束递归。
> 
> ❞

### Show me the Code ###

**C**

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
        /* 两个链表其中一个为空，递归结束 */
        if(l1 == NULL || l2 == NULL) {
            return l1 == NULL ? l2 : l1;
        }
            
        /* 其中一个链表的头节点的值小于另一个，则选值较小者作为新链表头节点 */    
        if(l1->val < l2->val) {
            /* 将该链表的剩余部分（子链表）跟另一个合并 */
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
    }

**C++**

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr || l2 == nullptr) {
            return l1 == nullptr ? l2 : l1;
        }
            
        if(l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
    }

**Java**

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
            
        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }

**Python3**

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None or l2 is None:
            return l2 if l1 is None else l1
        
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next);
            return l2;

**Golang**

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
        if l1 == nil {
            return l2
        } else if l2 == nil {
            return l1
        }
    
        if l1.Val < l2.Val {
            l1.Next = mergeTwoLists(l1.Next, l2)
            return l1
        } else {
            l2.Next = mergeTwoLists(l1, l2.Next)
            return l2
        }
    }

**复杂度分析**

时间复杂度：**O(n + m)**，其中 n 和 m 分别为两个链表的长度，需要递归调用两个链表的每个节点一次。

空间复杂度：**O(n + m)**。

## 方法二：迭代 ##

除了采用递归外，还可以采用迭代的方法，具体如何操作，如下例子所示：

**举例**

以链表l1: 1->4->null 和链表l2: 2->3->null 为例。

![89122d283e41cb753d03ecf8f9841ce8.png][] 例子

设置两个指针 cur1 和 cur2，分别指向两个链表的头节点；

![dfec0a857e6fd4ee648b93297d7134b3.png][] 设置指针

比较 cur1 和 cur2 指向的节点的值的大小，右移指向的节点值较小的 cur1；

![0f9de51cfbc73a4c4d176d3d6c9c68d2.png][] 比较节点值大小，并移动节点值较小的指针

设置一个指针 pre1，记录上次比较时值较小的节点；

![2314b31b74c5a2f040184439d183c24e.png][] 设置一个节点，记录上一步右移前其指向的节点

设置一个指针 next，记录 cur2 指向节点的下一节点；

![298f1dfed99e3e9621f9c6ef2cd4f221.png][] 记录 cur2 下一节点

由于 pre1 指向的节点值小于 cur2 指向的节点值，连接它们；

![e96dd81931d42cd83e3e42bff6b48d9c.png][] 新链表的头节点与第二个节点连接

同时由于 cur2 指向的节点小于 cur1 指向的节点，连接它们；

![bf12624c3bb71fa3be1bdfe5b23450e6.png][] 连接新链表

右移 pre1 和 cur2 分别到 cur2 和 next 位置；

![38981d0a4751dbeded8b2de353a23716.png][] 移动指针

由于 cur1 指向的节点值大于 cur2 指向的节点值，将 pre1 指向的节点连接 cur2 指向的节点；

![be45ba2f0a7bc3ddb240327fb4b49def.png][] 比较判断，重新获取第三个节点

由于 cur2 指向的节点值小于 cur1 指向的节点值，连接它们；

![0313c24761aa378781ae36bdedd233d1.png][] 获取新链表的第四个节点

采用迭代法，合并两个上升链表到一个的完整过程，如下动图示：

![99b294dd25ea9c72583cda6d6df10b47.gif][] 迭代法的完整操作过程

### Show me the Code ###

**C**

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
        if (l1 == NULL || l2 == NULL) {
            return l1 != NULL ? l1 : l2;
        }
    
        struct ListNode* mergeHead = l1->val > l2->val ? l2 : l1;  
        struct ListNode* cur1 = mergeHead == l1 ? l1 : l2;         
        struct ListNode* cur2 = mergeHead == l1 ? l2 : l1;
        /* 记录上次比较时节点值小的节点 */
        struct ListNode* pre = NULL;  
        /* 记录当前节点值大的节点的下一节点 */                              
        struct ListNode* next = NULL;
        while (cur1 != NULL && cur2 != NULL) {
            if (cur1->val <= cur2->val) {
                pre = cur1;
                cur1 = cur1->next;
            } else {
                next = cur2->next;  
                /* 将值较小的节点连接到另一链表节点值大的节点 */
                pre->next = cur2;   
                /* 将另一链表中节点值大的节点连接到值较小的节点的下一节点 */
                cur2->next = cur1;  
                pre = cur2;
                cur2 = next;            
            }
        }
        /* 合并后 l1 和 l2 最多有一个未被合并完，链表末尾指向未合并完的链表 */
        pre->next = cur1 == NULL ? cur2 : cur1;
        return mergeHead;
    }

**C++**

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr || l2 == nullptr) {
            return l1 != nullptr ? l1 : l2;
        }
    
        ListNode* pre = nullptr;                              
        ListNode* next = nullptr;
        ListNode* mergeHead = l1->val > l2->val ? l2 : l1;  
        ListNode* cur1 = mergeHead == l1 ? l1 : l2;         
        ListNode* cur2 = mergeHead == l1 ? l2 : l1;        
        while (cur1 != nullptr && cur2 != nullptr) {
            if (cur1->val <= cur2->val) {
                pre = cur1;
                cur1 = cur1->next;
            } else {
                next = cur2->next;  
                pre->next = cur2;   
                cur2->next = cur1;  
                pre = cur2;
                cur2 = next;            
            }
        }
    
        pre->next = cur1 == nullptr ? cur2 : cur1;
        return mergeHead;
    }

**Java**

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 != null ? l1 : l2;
        }
    
        ListNode pre = null;                              
        ListNode next = null;
        ListNode mergeHead = l1.val > l2.val ? l2 : l1;  
        ListNode cur1 = mergeHead == l1 ? l1 : l2;         
        ListNode cur2 = mergeHead == l1 ? l2 : l1;        
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre = cur1;
                cur1 = cur1.next;
            } else {
                next = cur2.next;  
                pre.next = cur2;   
                cur2.next = cur1;  
                pre = cur2;
                cur2 = next;            
            }
        }
    
        pre.next = cur1 == null ? cur2 : cur1;
        return mergeHead;
    }

**复杂度分析**

时间复杂度：**O(n + m)**，其中 n 和 m 分别为两个链表的长度，需要遍历两个链表的每个节点。

空间复杂度：**O(1)**，未开辟额外空间。

## 链表往期精彩回顾 ##

[链表问题，如何优雅递龟？][Link 1]

[互联网算法面试题之旋转链表][Link 2]

[动图：删除链表的倒数第 N 个结点][N]

[快慢指针---不就是快指针走两步慢指针走一步嘛？][---]

## 更多精彩 ##

关注公众号**程序员小熊**

![163037598939bce48b224f75b0840bb5.png][] 微信公众号

回复**512**，即可获取**算法小抄电子书**

回复**C++**，即可获取**侯捷老师的C++视频教程**

回复**算法**，即可获取**高清无码的经典算法电子书**

回复**python**，即可获取**高清无码的经典python电子书**

回复**1024**，即可获取**三份BAT大佬的Leetcode刷题手册**

**为了回馈读者，本公众号不定期会有送礼活动，敬请关注**

**点“赞”和“在看”哦****![e8b3dab9397d349da2ffda87933295fa.gif][]**

[62914de4f42ad74278440822aa56496e.png]: https://img-blog.csdnimg.cn/img_convert/62914de4f42ad74278440822aa56496e.png
[d81c33342d7a45837a25674c35d9d8d4.png]: /images/20220829/d44aa03859d44650895e3d7170cc126c.png
[89122d283e41cb753d03ecf8f9841ce8.png]: /images/20220829/20abf44a4e1245fca4ad6d712fd2f85b.png
[dfec0a857e6fd4ee648b93297d7134b3.png]: /images/20220829/f821bc6254ba43e787998e1a3073a595.png
[0f9de51cfbc73a4c4d176d3d6c9c68d2.png]: /images/20220829/01056f20381e4d1f8a50c0b913c1008f.png
[2314b31b74c5a2f040184439d183c24e.png]: /images/20220829/5277d52346e74a34ba19defdede23acf.png
[298f1dfed99e3e9621f9c6ef2cd4f221.png]: /images/20220829/a7c7d8a70bb54b2c8d907da37395072a.png
[e96dd81931d42cd83e3e42bff6b48d9c.png]: /images/20220829/d6e3fe0a107940b5a6b8c1bc3acdc035.png
[bf12624c3bb71fa3be1bdfe5b23450e6.png]: /images/20220829/efbdd4b321ed4f97b0826f5779e4010d.png
[38981d0a4751dbeded8b2de353a23716.png]: /images/20220829/f121482cd30b47b3b80d3c9170cee9bf.png
[be45ba2f0a7bc3ddb240327fb4b49def.png]: /images/20220829/5d1d968b75aa49b7b4c5487d7994f584.png
[0313c24761aa378781ae36bdedd233d1.png]: /images/20220829/b9a67c699f96440db3a7b9f49b6c9870.png
[99b294dd25ea9c72583cda6d6df10b47.gif]: /images/20220829/52d3fd4510b34d2484535e5f338aed58.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzkzMDI2NTA5Mw%3D%3D&idx=1&lang=zh_CN&mid=2247492206&scene=21&sn=2dc54b1094350dee918bd2436cfd3897&token=597443172#wechat_redirect
[Link 2]: https://mp.weixin.qq.com/s?__biz=MzkzMDI2NTA5Mw%3D%3D&idx=1&lang=zh_CN&mid=2247492181&scene=21&sn=f46b302238b6759dc4a292d993a7ff56&token=597443172#wechat_redirect
[N]: https://mp.weixin.qq.com/s?__biz=MzkzMDI2NTA5Mw%3D%3D&idx=1&lang=zh_CN&mid=2247492173&scene=21&sn=533783fe5accb5880e5788445b3121b8&token=597443172#wechat_redirect
[---]: https://mp.weixin.qq.com/s?__biz=MzkzMDI2NTA5Mw%3D%3D&idx=1&lang=zh_CN&mid=2247492193&scene=21&sn=0d4015150266abfd1f5fbf3758c58a4d&token=597443172#wechat_redirect
[163037598939bce48b224f75b0840bb5.png]: /images/20220829/ff5d6eaeb80f431e92dad6fe61e81a34.png
[e8b3dab9397d349da2ffda87933295fa.gif]: /images/20220829/6345afe6afd34c78b768510423f53d1b.png