【经典算法】LeetCode 21:合并两个有序链表Java/C/Python3实现含注释说明,Easy)

合并两个有序链表

  • 题目描述
  • 思路及实现
    • 方式一：迭代（推荐）
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
      • 复杂度分析
    • 方式二：递归（不推荐）
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
      • 复杂度分析
  • 总结
  • 相似题目

  • 标签：字符串处理、前缀判断

题目描述

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

示例 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 均按 非递减顺序 排列

原题： LeetCode 21

思路及实现

方式一：迭代（推荐）

思路

我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位

代码实现

Java版本
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *     }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode node = new ListNode(-1); // 创建一个临时节点作为结果链表的头节点
        ListNode cur = node;
        
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1; // 将较小节点连接到结果链表
                list1 = list1.next; // 移动指针到下一个节点
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next; // 移动当前节点指针到下一个节点
        }
        
        if (list1 != null) {
            cur.next = list1; // 将剩下的节点连接到结果链表
        }
        
        if (list2 != null) {
            cur.next = list2;
        }
        
        return node.next; // 返回结果链表的头节点
    }
}

说明：
创建了一个临时节点作为结果链表的头节点。然后使用cur引用指向当前节点，通过遍历两个链表，比较节点的值，将较小节点连接到结果链表中，并将指针移向下一个节点。最后，将剩下的节点连接到结果链表的末尾。

需要注意的是，最后返回的是结果链表的头节点

C语言版本
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = -1; // 创建一个临时节点作为结果链表的头节点
    node->next = NULL;
    struct ListNode* cur = node;
    
    while (list1 != NULL && list2 != NULL) {
        if (list1->val < list2->val) {
            cur->next = list1; // 将较小节点连接到结果链表
            list1 = list1->next; // 移动指针到下一个节点
        } else {
            cur->next = list2;
            list2 = list2->next;
        }
        cur = cur->next; // 移动当前节点指针到下一个节点
    }
    
    if (list1 != NULL) {
        cur->next = list1; // 将剩下的节点连接到结果链表
    }
    
    if (list2 != NULL) {
        cur->next = list2;
    }
    
    struct ListNode* result = node->next; // 指向结果链表的头节点
    free(node); // 释放临时节点的内存
    return result;
}

说明： 在C语言中使用了头节点，并使用了指针操作来完成。

在算法中，我们创建了一个临时节点作为结果链表的头节点。然后使用cur指针指向当前节点，通过遍历两个链表，比较节点的值，将较小节点连接到结果链表中，并将指针移向下一个节点。最后，将剩下的节点连接到结果链表的末尾。

需要注意的是，最后返回的是结果链表的头节点，使用一个临时节点来保存结果链表的头节点可以简化操作。

在末尾，我们释放了临时节点的内存，以防止内存泄漏。

Python3版本
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        node = ListNode(-1)  # 创建临时节点作为结果链表的头节点
        cur = node
        
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1  # 将较小节点连接到结果链表
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        
        cur.next = list1 or list2  # 将剩下的节点连接到结果链表
        
        return node.next  # 返回结果链表的头节点

说明： Python 三元表达式写法 A if x else B ，代表当 x=True 时执行 A ，否则执行 B 。

复杂度分析

  • 时间复杂度：O(M+N)，M, N分别标识list1和list2的长度
  • 空间复杂度: O(1), 节点引用cur，常量级的额外空间

方式二：递归（不推荐）

思路

我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：

情况一   ：list1[0]<list2[0]，则 list1[0]+merge(list1[1:],list2) 
其他情况 ：list2[0]+merge(list1,list2[1:])

也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

我们直接将以上递归过程建模，同时需要考虑边界情况。
如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束

代码实现

Java版本
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 如果l1为空，则直接返回l2作为合并后的链表
        if (l1 == null) {
            return l2;
        }
        // 如果l2为空，则直接返回l1作为合并后的链表
        else if (l2 == null) {
            return l1;
        }
        // 如果l1的值小于l2的值
        else if (l1.val < l2.val) {
            // 将l1的下一个节点与l2递归地合并
            l1.next = mergeTwoLists(l1.next, l2);
            return l1; // 返回合并后的链表头节点l1
        }
        // 如果l2的值小于等于l1的值
        else {
            // 将l2的下一个节点与l1递归地合并
            l2.next = mergeTwoLists(l1, l2.next);
            return l2; // 返回合并后的链表头节点l2
        }
    }
}

说明：
解法提供了递归方式来合并两个有序链表的操作。在算法中，首先处理特殊情况：如果l1为空，则直接返回l2作为合并后的链表；如果l2为空，则直接返回l1作为合并后的链表。接下来，判断l1和l2的值大小关系：如果l1的值小于l2的值，将l1的下一个节点与l2递归地合并，将合并结果作为l1的下一个节点，并返回l1作为合并后的链表头节点；如果l2的值小于等于l1的值，将l2的下一个节点与l1递归地合并，将合并结果作为l2的下一个节点，并返回l2作为合并后的链表头节点。最终，返回合并后的链表头节点。

C语言版本
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    // 如果l1为空，则直接返回l2作为合并后的链表
    if (l1 == NULL) {
        return l2;
    }
    // 如果l2为空，则直接返回l1作为合并后的链表
    else if (l2 == NULL) {
        return l1;
    }
    // 如果l1的值小于l2的值
    else if (l1->val < l2->val) {
        // 将l1的下一个节点与l2递归地合并
        l1->next = mergeTwoLists(l1->next, l2);
        return l1; // 返回合并后的链表头节点l1
    }
    // 如果l2的值小于等于l1的值
    else {
        // 将l2的下一个节点与l1递归地合并
        l2->next = mergeTwoLists(l1, l2->next);
        return l2; // 返回合并后的链表头节点l2
    }
}

说明：
在算法中，首先处理特殊情况：如果l1为空，则直接返回l2作为合并后的链表；如果l2为空，则直接返回l1作为合并后的链表。接下来，判断l1和l2的值的大小关系：如果l1的值小于l2的值，将l1的下一个节点与l2递归地合并，将合并结果作为l1的下一个节点，并返回l1作为合并后的链表头节点；如果l2的值小于等于l1的值，将l2的下一个节点与l1递归地合并，将合并结果作为l2的下一个节点，并返回l2作为合并后的链表头节点。最终，返回合并后的链表头节点。

Python3版本
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:  # 如果l1为空，则直接返回l2
            return l2
        elif not l2:  # 如果l2为空，则直接返回l1
            return l1
        elif l1.val < l2.val:  # 如果l1的值小于l2的值
            l1.next = self.mergeTwoLists(l1.next, l2)  # 递归地将l1的下一个节点与l2合并
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)  # 递归地将l2的下一个节点与l1合并
            return l2

复杂度分析

  • 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。
  • 空间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。

总结

递归和迭代都可以用来解决将两个有序链表合并的问题。下面对比一下递归和迭代的解法特点：

递归解法迭代解法
优点简洁，易于理解和实现不涉及函数递归调用，避免递归开销和栈溢出问题
缺点可能产生多个函数调用，涉及函数调用开销和栈溢出问题需要使用额外变量保存当前节点，增加代码复杂性
时间复杂度O(m+n)，其中m和n分别是两个链表的长度O(m+n)，其中m和n分别是两个链表的长度
空间复杂度O(m+n)，其中m和n分别是两个链表的长度O(1)

在实际应用中，如果链表较长，特别是超过系统栈的容量，采用迭代解法更为安全。而对于简短的链表，递归解法更为简洁和直观。

相似题目

题目难度链接
LeetCode 21 合并两个有序链表简单链接
LeetCode 23 合并K个有序链表困难链接
LeetCode 88 合并两个有序数组简单链接
LeetCode 56 合并区间中等链接

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/506610.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LLM大语言模型（八）：ChatGLM3-6B使用的tokenizer模型BAAI/bge-large-zh-v1.5

LLM大语言模型（八）：ChatGLM3-6B使用的tokenizer模型BAAI/bge-large-zh-v1.5

背景 BGE embedding系列模型是由智源研究院研发的中文版文本表示模型。 可将任意文本映射为低维稠密向量&#xff0c;以用于检索、分类、聚类或语义匹配等任务&#xff0c;并可支持为大模型调用外部知识。 BAAI/BGE embedding系列模型 模型列表 ModelLanguageDescriptionq…
阅读更多...
《QT实用小工具·五》串口助手

《QT实用小工具·五》串口助手

1、概述 源码放在文章末尾 该项目实现了串口助手的功能&#xff0c;可在界面上通过串口配置和网络配置进行串口调试。 基本功能 支持16进制数据发送与接收。支持windows下COM9以上的串口通信。实时显示收发数据字节大小以及串口状态。支持任意qt版本&#xff0c;亲测4.7.0 到…
阅读更多...
[leetcode] 100. 相同的树

[leetcode] 100. 相同的树

给你两棵二叉树的根节点 p 和 q &#xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是相同的。 示例 1&#xff1a; 输入&#xff1a;p [1,2,3], q [1,2,3] 输出&#xff1a;true示例 2&a…
阅读更多...
微信小程序【从入门到精通】——服务器的数据交互

微信小程序【从入门到精通】——服务器的数据交互

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…
阅读更多...
【设计】6种ID生成策略描述，优点 ，缺点 ，适用场景

【设计】6种ID生成策略描述，优点 ，缺点 ，适用场景

1.数据库自增ID 描述 自增Id是在设计表时将id字段的值设置为自增的形式&#xff0c;这样当插入一行数据时无 需指定id会自动根据前一字段的Id值1进行填充 优点 主键自动增长&#xff0c;不用手工设值、数字型&#xff0c;占用空间小、检索非常有利、有顺序&#xff0c;不会…
阅读更多...
08、JS实现：数组两数之和算法的两种解决方案(一步一步剖析，很详细)

08、JS实现：数组两数之和算法的两种解决方案(一步一步剖析，很详细)

数组两数之和的算法 Ⅰ、数组两数之和算法的方案一&#xff1a;1、题目描述&#xff1a;2、解题思路&#xff1a;3、实现代码&#xff1a; Ⅱ、数组两数之和算法的方案二&#xff1a;1、实现代码&#xff1a; Ⅲ、小结&#xff1a; Ⅰ、数组两数之和算法的方案一&#xff1a; …
阅读更多...
51单片机学习笔记11 使用DS18B20温度传感器

51单片机学习笔记11 使用DS18B20温度传感器

51单片机学习笔记11 使用DS18B20温度传感器 一、DS18B20简介1. 主要特点2. 工作原理3. 引脚说明4. ROM 二、1-wire协议简介1. 总线结构&#xff1a;2. 通信方式&#xff1a;3. 数据传输&#xff1a;4. 设备识别&#xff1a;5. 供电方式&#xff1a;6. 应用场景&#xff1a;7. 优…
阅读更多...
vue页面实现旋转饼图

vue页面实现旋转饼图

一、示例图片 二、参考 3D饼图-半透明 - ECharts图表集,echarts gallery社区,Make A Pie,分享你的可视化作品isqqw.com 三、实现 1、自定义组件RotatingPieChart.vue <template><div>【旋转饼图】</div><div ref"chart" class"chart-c…
阅读更多...
C语言单链表的窗口化操作

C语言单链表的窗口化操作

#include <stdio.h> #include <stdlib.h>// 定义链表的节点结构 struct Node {int data;struct Node* next; };// 初始化链表 void initialize(struct Node** head) {*head NULL; }// 在链表末尾插入节点 void insert(struct Node** head, int value) {// 创建新节…
阅读更多...
基于BEV的自动驾驶会颠覆现有的自动驾驶架构吗

基于BEV的自动驾驶会颠覆现有的自动驾驶架构吗

基于BEV的自动驾驶会颠覆现有的自动驾驶架构吗 引言 很多人都有这样的疑问–基于BEV(Birds Eye View)的自动驾驶方案是什么&#xff1f;这个问题&#xff0c;目前学术界还没有统一的定义&#xff0c;但从我的开发经验上&#xff0c;尝试做一个解释&#xff1a;以鸟瞰视角为基础…
阅读更多...
Web框架开发-Form组件和ajax实现注册

Web框架开发-Form组件和ajax实现注册

一、注册相关的知识点 1、Form组件 我们一般写Form的时候都是把它写在views视图里面，那么他和我们的视图函数也不影响，我们可以吧它单另拿出来，在应用下面建一个forms.py的文件来存放 2、局部钩子函数 1 2 3 4 5 6 7 # 局部钩子函数 def clean_username(self): userna…
阅读更多...
《QT实用小工具·六》代码行数统计工具

《QT实用小工具·六》代码行数统计工具

1、概述 源码放在文章末尾 该项目实现了对不同编程语言文件的代码行数的统计 统计的内容包含&#xff1a; 1、代码行数 2、注释行数 3、空白行数 下面是demo演示&#xff1a; 项目部分代码如下所示&#xff1a; #pragma execution_character_set("utf-8")#inclu…
阅读更多...
区块链食品溯源案例实现（一）

区块链食品溯源案例实现（一）

引言&#xff1a; 食品安全问题一直是社会关注的热点&#xff0c;而食品溯源作为解决食品安全问题的重要手段&#xff0c;其重要性不言而喻。传统的食品溯源系统往往存在数据易被篡改、信息不透明等问题&#xff0c;而区块链技术的引入&#xff0c;为食品溯源带来了革命性的变革…
阅读更多...
【ProComponents】解决 ProTable 中 params 参数改变，request 函数未触发问题

【ProComponents】解决 ProTable 中 params 参数改变，request 函数未触发问题

文章目录 先建议自查下官方文档&#xff0c;了解params和request直接的关系 确定params绑定的参数是否改变&#xff0c;例如 user_name 参数 import { ProTable, WxIcon } from /components; import { getSearchParams } from ice; import { useEffect, useMemo, useRef, useS…
阅读更多...
智慧公厕是什么？智慧公厕的主要功能、特点？

智慧公厕是什么？智慧公厕的主要功能、特点？

智慧公厕&#xff0c;顾名思义&#xff0c;是指应用了智能科技的公共厕所&#xff0c;旨在提供更加便捷、舒适、智能化的卫生服务。相比传统的公厕&#xff0c;智慧公厕不仅拥有更加智能化的设备&#xff0c;还配备了远程监控与管理系统&#xff0c;以及节能环保技术&#xff0…
阅读更多...
优化页面加载时间：改善用户体验的关键

优化页面加载时间：改善用户体验的关键

✨✨ 祝屏幕前的您天天开心&#xff0c;每天都有好运相伴。我们一起加油&#xff01;✨✨ &#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; 目录 引言 一、为什么页面加载时间重要&#xff1f; 二、如何减少页面加载时间&#xff1f; …
阅读更多...
SiLM824x系列SiLM8244 配置为高、低边驱动 支持死区可编程，隔离双通道门级驱动器

SiLM824x系列SiLM8244 配置为高、低边驱动 支持死区可编程，隔离双通道门级驱动器

SiLM824x系列SiLM8244是一款具有不同配置的隔离双通道门极驱动器。SiLM8244配置为高、低边驱动&#xff0c;SiLM8244可提供4A的输出源电流和6A的灌电流能力&#xff0c;并且其驱动输出电压可以支持到33V。支持死区可编程&#xff0c;通过调整DT脚外部的电阻大小&#xff0c;调整…
阅读更多...
基于单片机汽车超声波防盗系统设计

基于单片机汽车超声波防盗系统设计

**单片机设计介绍&#xff0c;基于单片机汽车超声波防盗系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机汽车超声波防盗系统设计概要主要涉及利用超声波传感器和单片机技术来实现汽车的安全防盗功能。以下是对…
阅读更多...
注册接口和前置SQL及数据生成及封装

注册接口和前置SQL及数据生成及封装

注册接口 演示注册接口的三步操作&#xff1a;【注册流程逻辑】 第一步&#xff1a;发送注册短信验证码接口请求 请求方法&#xff1a; put 请求地址&#xff1a;http://shop.lemonban.com:8107/user/sendRegisterSms 请求参数&#xff1a;{“mobile”:“13422337766”} 请求头…
阅读更多...
【面试专题】Mybatis高频面试题

【面试专题】Mybatis高频面试题

一、介绍下MyBatis中的工作原理 1。介绍MyBatis的基本情况&#xff1a;ORM 2。原理&#xff1a; MyBatis框架的初始化操作处理SQL请求的流程 1.系统启动的时候会加载解析全局配置文件和对应映射文件。加载解析的相关信息存储在 Configuration 对象 Testpublic void test1(…
阅读更多...
最新文章

Copyright @ 2022~2023