高频面试题之链表专题-合并两个有序单链表，要求合并后依旧有序

朱雀 2022-10-15 09:00 88阅读 0赞

# **1、合并两个有序单链表，要求合并后依旧有序。**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][] #

OJ链接：[https://leetcode-cn.com/problems/merge-two-sorted-lists/description/][https_leetcode-cn.com_problems_merge-two-sorted-lists_description]

**高频考察的大厂云图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1][]

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

示例 1：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 2][]

输入：l1 = \[1,2,4\], l2 = \[1,3,4\]  
输出：\[1,1,2,3,4,4\]

示例 2：

输入：l1 = \[\], l2 = \[\]  
输出：\[\]

示例 3：

输入：l1 = \[\], l2 = \[0\]  
输出：\[0\]

提示：

*  两个链表的节点数目范围是 \[0, 50\]
 *  \-100 <= Node.val <= 100
 *  l1 和 l2 均按 非递减顺序 排列

### 提供代码 ###

### 解题思路 ###

取小的尾插

先创建一个空链表头节点，然后依次从两个有序链表中选取最小的进行尾插操作进行合并。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 3][]

尾插小技巧：一般要整出一个头结点，为了防止第一次与第二次及以后的尾插不同

### **代码实现：** ###

/**
     * 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) {
            if(l1==NULL)
                return l2;
            if(l2==NULL)
                return l1;
            ListNode* head, * tail;
            head = tail = new ListNode;
    
            //取小的尾插
            while (l1 && l2)
            {
                if (l1->val < l2->val)
                {
                    tail->next = l1;
                    l1= l1->next;
                }
                else if(l1->val>l2->val)
                {
                    tail->next = l2;
                    l2 = l2->next;
                }
                else
                {
                    tail->next = l1;
                    l1= l1->next;
                    tail = tail->next;
                    tail->next = l2;
                    l2 = l2->next;
                }
                tail = tail->next;
            }
            if (l1 != NULL)
                tail->next = l1;
            else if (l2 != NULL)
                tail->next = l2;
    
            //释放防止内存泄露
            ListNode* l = head->next;
            delete head;
            return l;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221014/43ac875c29124fa699cf68eb2f2121f0.png
[https_leetcode-cn.com_problems_merge-two-sorted-lists_description]: https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1]: /images/20221014/2dbc7a06a6e64fa9a2eb2155b4976eaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 2]: /images/20221014/5b3d79c924684a43808e4bcfed153bfe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 3]: /images/20221014/73658234f9824869a5440e93d1c970d1.png