21.合并两个有序链表

LeetCode LeetCode 链表 递归
发布时间 :
字数:2.8k 阅读 : 评论:
  1. 21.合并两个有序链表
    1. 21.1 题目
    2. 21.2 题解
      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 题解

不使用头结点迭代遍历拼接

// 方法一：不使用头结点迭代遍历拼接
// 不使用头结点的话对初始化进行判断有点麻烦。而且是复制值，其实可以直接指到新节点原列表往后移，不用复制值。存在重复的代码，最后的处理某个链表还有剩余节点的情况可以优化。
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;
    }
}

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-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏