21.合并两个有序链表

LeetCode LeetCode 热题100 链表 递归
发布时间 :
字数:3.9k 阅读 : 评论:
  1. 21.合并两个有序链表
    1. 21.1 题目
    2. 21.2 题解
      1. 方法一：不使用头结点迭代遍历拼接
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：使用头结点迭代遍历拼接
        1. 思路
        2. 复杂度分析
        3. 代码
      3. 方法三：递归合并链表
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 21.3 代码
    4. 21.4 运行结果

21.合并两个有序链表

21.1 题目

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

示例：

  • 示例 1：

    • 输入：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 均按非递减顺序排列

21.2 题解

方法一：不使用头结点迭代遍历拼接

思路

不使用虚拟头节点，直接构建新链表。每次比较两个链表当前节点的值，将较小的节点值复制到新链表中。需要处理边界情况：链表为空、只剩一个链表有节点等。

具体步骤：

  1. 如果两个链表都为空，返回 null。
  2. 初始化结果链表和当前指针。
  3. 遍历两个链表，比较当前节点值：
    • 将较小值复制到新节点，接到结果链表末尾。
    • 移动对应链表的指针。
  4. 处理剩余节点：将未遍历完的链表剩余节点复制到结果链表。

举例：对于 l1 = [1,2,4], l2 = [1,3,4]：

  • 比较 1 和 1，取 1，结果：[1]，l1 后移
  • 比较 2 和 1，取 1，结果：[1,1]，l2 后移
  • 比较 2 和 3，取 2，结果：[1,1,2]，l1 后移
  • 比较 4 和 3，取 3，结果：[1,1,2,3]，l2 后移
  • 比较 4 和 4，取 4，结果：[1,1,2,3,4]，l1 后移
  • l1 为空，复制 l2 剩余的 4，结果：[1,1,2,3,4,4]

注意：此方法代码较冗长，存在重复代码，推荐使用方法二或方法三。

复杂度分析

  • 时间复杂度：O(m + n)，遍历两个链表。
  • 空间复杂度：O(m + n)，创建新节点。

代码

// 方法一：不使用头结点迭代遍历拼接
// 不使用头结点的话对初始化进行判断有点麻烦。而且是复制值，其实可以直接指到新节点原列表往后移，不用复制值。存在重复的代码，最后的处理某个链表还有剩余节点的情况可以优化。
static ListNode MergeTwoLists1(ListNode list1, ListNode list2)
{
    // 如果两个链表均为空，直接返回空
    if (list1 == null && list2 == null)
    {
        return null;
    }

    // 初始化两个当前节点指针分别指向两个链表的头节点
    ListNode nowList1Node = list1;
    ListNode nowList2Node = list2;

    // 初始化合并后的链表头节点和当前节点指针
    ListNode resultList = null;
    ListNode nowResultListNode = null;

    // 遍历两个链表，比较当前节点的值，将较小的值加入到新链表中
    while (nowList1Node != null && nowList2Node != null)
    {
        // 如果结果链表为空，说明是第一个节点
        if (resultList == null)
        {
            resultList = new ListNode();
            nowResultListNode = resultList;
        }
        else
        {
            // 否则，创建新节点，并将当前节点的 next 指向新节点
            nowResultListNode.next = new ListNode();
            nowResultListNode = nowResultListNode.next;
        }

        // 比较当前两个链表节点的值，将较小的值加入到新链表
        if (nowList1Node.val <= nowList2Node.val)
        {
            nowResultListNode.val = nowList1Node.val;
            nowList1Node = nowList1Node.next;
        }
        else
        {
            nowResultListNode.val = nowList2Node.val;
            nowList2Node = nowList2Node.next;
        }
    }

    // 处理某个链表还有剩余节点的情况
    if (nowList1Node == null)
    {
        while (nowList2Node != null)
        {
            // 如果结果链表为空，说明是第一个节点
            if (resultList == null)
            {
                resultList = new ListNode();
                nowResultListNode = resultList;
            }
            else
            {
                // 否则，创建新节点，并将当前节点的 next 指向新节点
                nowResultListNode.next = new ListNode();
                nowResultListNode = nowResultListNode.next;
            }

            // 将剩余节点的值加入到新链表
            nowResultListNode.val = nowList2Node.val;
            nowList2Node = nowList2Node.next;
        }
    }
    else if (nowList2Node == null)
    {
        while (nowList1Node != null)
        {
            // 如果结果链表为空，说明是第一个节点
            if (resultList == null)
            {
                resultList = new ListNode();
                nowResultListNode = resultList;
            }
            else
            {
                // 否则，创建新节点，并将当前节点的 next 指向新节点
                nowResultListNode.next = new ListNode();
                nowResultListNode = nowResultListNode.next;
            }

            // 将剩余节点的值加入到新链表
            nowResultListNode.val = nowList1Node.val;
            nowList1Node = nowList1Node.next;
        }
    }

    // 返回合并后的链表头节点
    return resultList;
}

方法二：使用头结点迭代遍历拼接

思路

使用虚拟头节点简化代码。创建一个虚拟头节点，用指针遍历两个链表，每次将较小的节点直接接到结果链表后面（不是复制值，而是直接改变指针）。最后将剩余链表直接接到结果链表末尾。

核心思想：虚拟头节点统一了「第一个节点」的处理逻辑，避免特殊判断。

具体步骤：

  1. 创建虚拟头节点 resultListHeadNode。
  2. 用 nowResultListNode 指针遍历构建结果链表。
  3. 遍历两个链表：
    • 比较 list1.val 和 list2.val
    • 将较小的节点接到 nowResultListNode.next
    • 移动对应链表的指针和 nowResultListNode
  4. 将剩余链表直接接到结果链表末尾。
  5. 返回虚拟头节点的下一个节点。

举例：对于 l1 = [1,2,4], l2 = [1,3,4]：

  • 虚拟头节点：dummy(0) → null
  • 比较 1 和 1，接 l1 的 1：dummy → 1，l1 后移
  • 比较 2 和 1，接 l2 的 1：dummy → 1 → 1，l2 后移
  • 比较 2 和 3，接 l1 的 2：dummy → 1 → 1 → 2，l1 后移
  • 比较 4 和 3，接 l2 的 3：dummy → 1 → 1 → 2 → 3，l2 后移
  • 比较 4 和 4，接 l1 的 4：dummy → 1 → 1 → 2 → 3 → 4，l1 后移
  • l1 为空，接 l2 剩余的 4：dummy → 1 → 1 → 2 → 3 → 4 → 4
  • 返回 dummy.next：[1,1,2,3,4,4]

复杂度分析

  • 时间复杂度：O(m + n)，遍历两个链表。
  • 空间复杂度：O(1)，只使用指针变量。

代码

// 方法二：使用头结点迭代遍历拼接
// 使用头结点同时原链表丢弃某节点前让结果链表指针直接指向该节点
static ListNode MergeTwoLists2(ListNode list1, ListNode list2)
{
    // 如果两个链表均为空，直接返回空
    if (list1 == null && list2 == null)
    {
        return null;
    }

    // 创建一个头节点，用于保存合并后的链表的头部信息
    ListNode resultListHeadNode = new ListNode(0);

    // 创建指针，用于遍历和构建合并后的链表
    ListNode nowResultListNode = resultListHeadNode;

    // 遍历两个链表，比较当前节点的值，将较小的值加入到新链表
    while (list1 != null && list2 != null)
    {
        // 如果 list1 的值小于 list2 的值
        if (list1.val < list2.val)
        {
            // 将 list1 的节点接入新链表，并将 list1 指针向后移动一位
            nowResultListNode.next = list1;
            list1 = list1.next;
        }
        else
        {
            // 将 list2 的节点接入新链表，并将 list2 指针向后移动一位
            nowResultListNode.next = list2;
            list2 = list2.next;
        }

        // 将 nowResultListNode 指针移动到新链表的尾部
        nowResultListNode = nowResultListNode.next;
    }

    // 处理某个链表还有剩余节点的情况，直接将剩余部分接入新链表
    nowResultListNode.next = list1 != null ? list1 : list2;

    // 返回合并后的链表头节点的下一个节点，因为头节点是用于辅助构建链表而不是存储实际数据的
    return resultListHeadNode.next;
}

方法三：递归合并链表

思路

递归思路：比较两个链表头节点的值，较小的节点作为合并后链表的头节点，其 next 指针指向递归合并剩余部分的结果。终止条件是其中一个链表为空。

核心思想：每次递归确定一个节点，将其 next 指向剩余部分的合并结果。

具体步骤：

  1. 如果 list1 为空，返回 list2。
  2. 如果 list2 为空，返回 list1。
  3. 比较 list1.val 和 list2.val：
    • 如果 list1.val <= list2.val：
      • list1.next 指向递归合并 list1.next 和 list2 的结果
      • 返回 list1
    • 否则：
      • list2.next 指向递归合并 list1 和 list2.next 的结果
      • 返回 list2

举例：对于 l1 = [1,2,4], l2 = [1,3,4]：

  • 比较 1 和 1，l1.val <= l2.val，l1.next = merge([2,4], [1,3,4])，返回 l1
    • 比较 2 和 1，l2.val < l1.val，l2.next = merge([2,4], [3,4])，返回 l2
      • 比较 2 和 3，l1.val < l2.val，l1.next = merge([4], [3,4])，返回 l1
        • 比较 4 和 3，l2.val < l1.val，l2.next = merge([4], [4])，返回 l2
          • 比较 4 和 4，l1.val <= l2.val，l1.next = merge(null, [4])，返回 l1
            • l1 为空，返回 l2 即 [4]
          • 返回 [4] → [4]
        • 返回 [3] → [4] → [4]
      • 返回 [2] → [3] → [4] → [4]
    • 返回 [1] → [2] → [3] → [4] → [4]
  • 最终结果：[1,1,2,3,4,4]

复杂度分析

  • 时间复杂度：O(m + n)，递归调用次数。
  • 空间复杂度：O(m + n)，递归调用栈深度。

代码

// 方法三：递归得当前节点和子节点
// 递归部分方法写返回当前节点的逻辑，当前节点指向的下一节点递归调用递归部分方法
static ListNode MergeTwoLists3(ListNode list1, ListNode list2)
{
    // 调用递归方法，返回合并后的链表头节点
    return ReturnMergeListNode(list1, list2);
}

static ListNode ReturnMergeListNode(ListNode list1, ListNode list2)
{
    // 如果链表1为空，则返回链表2，递归终止条件之一
    if (list1 == null) return list2;
    // 如果链表2为空，则返回链表1，递归终止条件之一
    if (list2 == null) return list1;

    // 如果链表1当前节点的值小于等于链表2当前节点的值
    if (list1.val <= list2.val)
    {
        // 递归调用，将链表1的下一个节点和链表2进行合并，然后将结果赋值给链表1的当前节点的next指针
        list1.next = ReturnMergeListNode(list1.next, list2);
        // 返回链表1的当前节点作为合并后链表的头节点
        return list1;
    }
    else
    {
        // 递归调用，将链表1和链表2的下一个节点进行合并，然后将结果赋值给链表2的当前节点的next指针
        list2.next = ReturnMergeListNode(list1, list2.next);
        // 返回链表2的当前节点作为合并后链表的头节点
        return list2;
    }
}

21.3 代码

using System;

public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

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

        // 示例 1：
        // 输入：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 均按 非递减顺序 排列

        #endregion

        #region 测试

        // 示例 1
        ListNode l1_1 = new ListNode(1);
        ListNode l1_2 = new ListNode(2);
        ListNode l1_4 = new ListNode(4);
        l1_1.next = l1_2;
        l1_2.next = l1_4;

        ListNode l2_1 = new ListNode(1);
        ListNode l2_3 = new ListNode(3);
        ListNode l2_4 = new ListNode(4);
        l2_1.next = l2_3;
        l2_3.next = l2_4;

        // ListNode result1 = MergeTwoLists1(l1_1, l2_1);
        // ListNode result1 = MergeTwoLists2(l1_1, l2_1);
        // ListNode result1 = MergeTwoLists3(l1_1, l2_1);
        ListNode result1 = MergeTwoLists3(l1_1, l2_1);
        PrintList(result1);

        // 示例 2
        ListNode l3 = null;
        ListNode l4 = null;

        // ListNode result2 = MergeTwoLists1(l3, l4);
        // ListNode result2 = MergeTwoLists2(l3, l4);
        ListNode result2 = MergeTwoLists3(l3, l4);
        PrintList(result2);

        // 示例 3
        ListNode l5 = null;
        ListNode l6 = new ListNode(0);

        // ListNode result3 = MergeTwoLists1(l5, l6);
        // ListNode result3 = MergeTwoLists2(l5, l6);
        ListNode result3 = MergeTwoLists3(l5, l6);
        PrintList(result3);

        #endregion
    }

    #region 答案

    // 方法一：不使用头结点迭代遍历拼接
    // 不使用头结点的话对初始化进行判断有点麻烦。而且是复制值，其实可以直接指到新节点原列表往后移，不用复制值。存在重复的代码，最后的处理某个链表还有剩余节点的情况可以优化。
    static ListNode MergeTwoLists1(ListNode list1, ListNode list2)
    {
        // 如果两个链表均为空，直接返回空
        if (list1 == null && list2 == null)
        {
            return null;
        }

        // 初始化两个当前节点指针分别指向两个链表的头节点
        ListNode nowList1Node = list1;
        ListNode nowList2Node = list2;

        // 初始化合并后的链表头节点和当前节点指针
        ListNode resultList = null;
        ListNode nowResultListNode = null;

        // 遍历两个链表，比较当前节点的值，将较小的值加入到新链表中
        while (nowList1Node != null && nowList2Node != null)
        {
            // 如果结果链表为空，说明是第一个节点
            if (resultList == null)
            {
                resultList = new ListNode();
                nowResultListNode = resultList;
            }
            else
            {
                // 否则，创建新节点，并将当前节点的 next 指向新节点
                nowResultListNode.next = new ListNode();
                nowResultListNode = nowResultListNode.next;
            }

            // 比较当前两个链表节点的值，将较小的值加入到新链表
            if (nowList1Node.val <= nowList2Node.val)
            {
                nowResultListNode.val = nowList1Node.val;
                nowList1Node = nowList1Node.next;
            }
            else
            {
                nowResultListNode.val = nowList2Node.val;
                nowList2Node = nowList2Node.next;
            }
        }

        // 处理某个链表还有剩余节点的情况
        if (nowList1Node == null)
        {
            while (nowList2Node != null)
            {
                // 如果结果链表为空，说明是第一个节点
                if (resultList == null)
                {
                    resultList = new ListNode();
                    nowResultListNode = resultList;
                }
                else
                {
                    // 否则，创建新节点，并将当前节点的 next 指向新节点
                    nowResultListNode.next = new ListNode();
                    nowResultListNode = nowResultListNode.next;
                }

                // 将剩余节点的值加入到新链表
                nowResultListNode.val = nowList2Node.val;
                nowList2Node = nowList2Node.next;
            }
        }
        else if (nowList2Node == null)
        {
            while (nowList1Node != null)
            {
                // 如果结果链表为空，说明是第一个节点
                if (resultList == null)
                {
                    resultList = new ListNode();
                    nowResultListNode = resultList;
                }
                else
                {
                    // 否则，创建新节点，并将当前节点的 next 指向新节点
                    nowResultListNode.next = new ListNode();
                    nowResultListNode = nowResultListNode.next;
                }

                // 将剩余节点的值加入到新链表
                nowResultListNode.val = nowList1Node.val;
                nowList1Node = nowList1Node.next;
            }
        }

        // 返回合并后的链表头节点
        return resultList;
    }

    // 方法二：使用头结点迭代遍历拼接
    // 使用头结点同时原链表丢弃某节点前让结果链表指针直接指向该节点
    static ListNode MergeTwoLists2(ListNode list1, ListNode list2)
    {
        // 如果两个链表均为空，直接返回空
        if (list1 == null && list2 == null)
        {
            return null;
        }

        // 创建一个头节点，用于保存合并后的链表的头部信息
        ListNode resultListHeadNode = new ListNode(0);

        // 创建指针，用于遍历和构建合并后的链表
        ListNode nowResultListNode = resultListHeadNode;

        // 遍历两个链表，比较当前节点的值，将较小的值加入到新链表
        while (list1 != null && list2 != null)
        {
            // 如果 list1 的值小于 list2 的值
            if (list1.val < list2.val)
            {
                // 将 list1 的节点接入新链表，并将 list1 指针向后移动一位
                nowResultListNode.next = list1;
                list1 = list1.next;
            }
            else
            {
                // 将 list2 的节点接入新链表，并将 list2 指针向后移动一位
                nowResultListNode.next = list2;
                list2 = list2.next;
            }

            // 将 nowResultListNode 指针移动到新链表的尾部
            nowResultListNode = nowResultListNode.next;
        }

        // 处理某个链表还有剩余节点的情况，直接将剩余部分接入新链表
        nowResultListNode.next = list1 != null ? list1 : list2;

        // 返回合并后的链表头节点的下一个节点，因为头节点是用于辅助构建链表而不是存储实际数据的
        return resultListHeadNode.next;
    }

    // 方法三：递归得当前节点和子节点
    // 递归部分方法写返回当前节点的逻辑，当前节点指向的下一节点递归调用递归部分方法
    static ListNode MergeTwoLists3(ListNode list1, ListNode list2)
    {
        // 调用递归方法，返回合并后的链表头节点
        return ReturnMergeListNode(list1, list2);
    }

    static ListNode ReturnMergeListNode(ListNode list1, ListNode list2)
    {
        // 如果链表1为空，则返回链表2，递归终止条件之一
        if (list1 == null) return list2;
        // 如果链表2为空，则返回链表1，递归终止条件之一
        if (list2 == null) return list1;

        // 如果链表1当前节点的值小于等于链表2当前节点的值
        if (list1.val <= list2.val)
        {
            // 递归调用，将链表1的下一个节点和链表2进行合并，然后将结果赋值给链表1的当前节点的next指针
            list1.next = ReturnMergeListNode(list1.next, list2);
            // 返回链表1的当前节点作为合并后链表的头节点
            return list1;
        }
        else
        {
            // 递归调用，将链表1和链表2的下一个节点进行合并，然后将结果赋值给链表2的当前节点的next指针
            list2.next = ReturnMergeListNode(list1, list2.next);
            // 返回链表2的当前节点作为合并后链表的头节点
            return list2;
        }
    }


    static void PrintList(ListNode head)
    {
        Console.Write("[");
        // 打印链表
        while (head != null)
        {
            string stringSplit = head.next == null ? "" : ",";
            Console.Write(head.val + stringSplit);
            head = head.next;
        }

        Console.Write("]");
        Console.WriteLine();
    }

    #endregion
}

21.4 运行结果

[1,1,2,3,4,4]
[]
[0]
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏