LeetCode如何合并两个有序链表-成都快上网建站

LeetCode如何合并两个有序链表

这篇文章将为大家详细讲解有关LeetCode如何合并两个有序链表,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

创新互联建站是一家专业提供元谋企业网站建设,专注与成都网站建设、成都做网站、HTML5、小程序制作等业务。10年已为元谋众多企业、政府机构等服务。创新互联专业的建站公司优惠进行中。

 

一、题目描述

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

  • 输入:1->2->4, 1->3->4
  • 输出:1->1->2->3->4->4
 

二、解题思路

 

2.1 迭代法

使用循环迭代的方法,依次找出较小的节点链接起来即可:

  • 比较 l1 和 l2 当前节点值的大小
  • 将较小的节点链接到 l3 尾部
  • l1 或 l2 指针后移一位
  • l3 指针后移一位
  • 循环结束:l1 和 l2 其中一个遍历到尾部
  • 将未遍历完的节点全部链接到 l3 尾部
  • 返回保存的 l3 头指针 head->next
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 1. 升序链表 l3
        ListNode *l3 = new ListNode(0);

        // 2. 保存头指针用于返回结果
        ListNode *head = l3;

        while (l1 && l2) {
            // 3. 选择较小的节点连接到 l3 尾部
            if (l1->val <= l2->val) {
                l3->next = l1;
                l1 = l1->next;
            } else {
                l3->next = l2;
                l2 = l2->next;
            }

            l3 = l3->next;
        }

        // 将多余的 l1 或者 l2 节点直接链接到 l3 尾部
        l3->next = (l1 == nullptr ? l2 : l1);

        return head->next;
    }
};
   
复杂度分析
  • 时间复杂度:O(m + n),循环的次数等于 2 个链表的总长度 m + n
  • 空间复杂度:O(1),使用的变量内存为常数级别
 

2.2 递归法

递归法要注意递归表达式和循环结束条件:

  • 当 l1 为空,返回 l2
  • 当 l2 为空,返回 l1
  • l1 和 l2 都不为空,比较节点 val
  • 将较小的节点链接上,并递归调用函数来确定下一个链接的节点

递归法不是很好理解,建议用 vs 调试看下内存。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 1. 递归结束条件
        if (l1 == nullptr)
            return l2;

        // 2. 递归结束条件
        if (l2 == nullptr)
            return l1;

        // 3. 递归表达式
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};
   
复杂度分析
  • 时间复杂度:O(m + n),每次递归都会添加一个链表节点,最终会递归 m + n 次
  • 空间复杂度:递归的过程中,会将全部 m + n 个节点都保存一次在递归调用栈中

关于“LeetCode如何合并两个有序链表”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。


名称栏目:LeetCode如何合并两个有序链表
网页URL:http://kswjz.com/article/ggihoh.html
扫二维码与项目经理沟通

我们在微信上24小时期待你的声音

解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流