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

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

时间:2024-04-03 12:58:48浏览次数:27  
标签:ListNode 21 next 链表 l2 Easy l1 节点

合并两个有序链表

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

题目描述

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

示例 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 合并区间中等链接

标签:ListNode,21,next,链表,l2,Easy,l1,节点
From: https://blog.csdn.net/qq_30757161/article/details/137217696

相关文章

  • AQY212GSX 固态继电器 PCB安装 SPST-NO 1A 60V
    AQY212GSX是一款由Panasonic公司规划和生产的继电器。它是一种SOP4光耦固态继电器,适用于各种电子设备中的信号切换和阻隔。该继电器的主要参数包括4-SOP4.4mm封装、工作温度规模为-40℃至+85℃、储存温度规模为-40℃至+100℃等。AQY212GSX继电器具有杰出的电气性能,如初始I/O......
  • KYOCERA Programming Contest 2021(AtCoder Beginner Contest 200)
    题目链接https://atcoder.jp/contests/abc200A-Century简单的abs(n-1)/100+1即可B-200thABC-200按题意写代码点击查看代码voidsolve(){intn,k;cin>>n>>k;for(inti=1;i<=k;i++){if(n%200==0)n/=200;elsen=n*1000+200;}......
  • SWUST OJ 952 单链表插入
    一、题目题目描述建立长度为n的单链表,在第i个结点之前插入数据元素data。输入第一行为自然数n,表示链式线性表的长度;第二行为n个自然数表示链式线性表各元素值;第三行为指定插入的位置i;第四行为待插入数据元素data。输出指定插入位置合法时候,输出插入元素后的链式线性......
  • P3521 [POI2011] ROT-Tree Rotations
    ​P3521[POI2011]ROT-TreeRotations线段树合并首先左右子树交换只会改变「跨过左右子树的逆序对」数量,对其他逆序对不会有任何影响,所以我们选择对每个结点的左右子树求解,判断是否交换。考虑对于每个节点建一个权值线段树,那么贡献就可以在merge操作中求解,原因是在权值线段......
  • P7219 [JOISC2020] 星座 3【笛卡尔树+整体dp】
    P7219[JOISC2020]星座3笛卡尔树+整体dp(线段树合并维护dp)考虑转化题意,不存在矩形为星座,即对于每个极大矩形中都只有一颗星星。而观察题目的方格,对于两个位置是否能够成为一个矩形,只和两个位置的区间最大值(小白船的位置)有关①。图中的红蓝矩形即为两个极大矩形。将删除星......
  • ABC221H Count Multiset
    传送门构造序列型DP。经典的就是这么一种构造序列的方式:用两种操作。增加一个\(0\)。将当前序列中所有数加\(1\)。由此可以构造出任意一种自然数不降序列。回到本题。即要求构造一个长度\(k\)和为\(n\)且没有一种数出现超过\(m\)次的不降序列,求方案数。考虑......
  • AIC2100人工智能程序编写
    用PythonAIC2100人工智能程序编写IC2100人工智能程序实验室 AIC21002.你必须严格遵守规范!任何拼写错误(包括空白和换行)都将导致扣分。如果要求您编写注释或文档字符串,则必须添加它们。如果某些Python库被禁止,导入它们将导致0分。根据实验室内容,可以添加其他规则。请仔细阅读规范文......
  • 链表
    template<typenameT>classthreadsafe_list{structnode//1{std::mutexm;std::shared_ptr<T>data;std::unique_ptr<node>next;node()://2next(){}node(Tconst&value)://3data(std......
  • 21_Shell脚本入门
    Shell脚本入门一、什么是shell脚本​我们已经能够熟练的在终端中输入命令来完成一些常用的操作,但是我们都是一条一条输入命令。这样会很麻烦,那么有没有一种方式可以将很多条命令放到一个文件里面,然后直接运行这个文件即可?肯定有,这个就是shell脚本!​shell脚本类似window......
  • 视频监控/云存储/AI智能分析平台EasyCVR集成时调用接口报跨域错误的原因排查
    EasyCVR视频融合平台基于云边端架构,可支持海量视频汇聚管理,能提供视频监控直播、云端录像、云存储、录像检索与回看、智能告警、平台级联、智能分析等视频服务。平台兼容性强,支持多协议、多类型设备接入,包括:国标GB/T28181协议、RTMP、RTSP/Onvif协议、海康Ehome、海康SDK、大华SDK......