【Leetcode刷题】算法：合并两个有序链表

约定不等于承诺〃 2023-10-10 18:58 28阅读 0赞

#### 文章目录 ####

*  一、题目介绍
 *  二、解决办法
 *  三、提交结果

## 一、题目介绍 ##

![在这里插入图片描述][e7a98dccf17d40069c931cf6dd8964c2.png]

## 二、解决办法 ##

首先定义一个名为ListNode的类：

class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next

ListNode代表一个链表节点，每个节点包含一个值（val）和一个指向下一个节点的指针（next）。

构造函数（init）被用来初始化ListNode类的实例。它接受两个参数：val和next。

val是节点的值，next是指向下一个节点的指针。这些参数都有默认值，如果没有提供参数，则val默认为0，next默认为None。

通过使用这个类，我们可以创建链表，并在每个节点中存储特定的值。例如，可以使用以下代码创建一个包含三个节点的链表：

node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    
    node1.next = node2
    node2.next = node3

在上面的示例中，node1是链表的第一个节点，它的值为1。node2是第二个节点，值为2，并且它的next指针指向node3。node3是最后一个节点，值为3，并且它的next指针为None，表示链表结束。

通过连接多个ListNode对象的next指针，可以构建一个完整的链表。这样，我们可以遍历链表并访问每个节点的值和指针，执行各种链表操作。

接下来，是合并两个链表：

class Solution:
        def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
            # 判断边界情况，如果其中一个链表为空，则直接返回另一个链表
            if not list1:
                return list2
            if not list2:
                return list1
    
            # 定义一个哨兵节点作为合并后链表的头节点
            head = ListNode(0)
            curr = head
    
            # 遍历两个链表，比较节点值，并将较小值的节点连接到合并后链表中
            while list1 and list2:
                if list1.val <= list2.val:
                    curr.next = list1
                    list1 = list1.next
                else:
                    curr.next = list2
                    list2 = list2.next
                curr = curr.next
    
            # 将剩余的节点连接到合并后链表的末尾
            if list1:
                curr.next = list1
            if list2:
                curr.next = list2
    
            return head.next

定义了一个类Solution。

mergeTwoLists方法接受两个参数：list1和list2，这两个参数都是ListNode类型的链表。

如果其中一个链表为空（即为None），则直接返回另一个链表。这是对边界情况的处理，确保在其中一个链表为空时，返回另一个非空链表。

定义一个哨兵节点（head）作为合并后链表的头节点，它的值为0。哨兵节点可以简化链表操作，最后返回head.next即为合并后的链表。

定义一个当前节点（curr），初始时指向头节点（head）。

进入一个循环，循环条件是list1和list2都不为空。在循环中，比较list1和list2当前节点的值，将较小值的节点连接到合并后链表中。

如果list1当前节点的值小于等于list2当前节点的值，则将list1当前节点连接到合并后链表中，并将list1指针后移。

如果list2当前节点的值小于list1当前节点的值，则将list2当前节点连接到合并后链表中，并将list2指针后移。

不断更新curr指针，指向合并后链表的最后一个节点。

当循环结束后，可能会有一个链表已经遍历完，但另一个链表还有剩余节点。如果list1还有剩余节点，则将剩余节点连接到合并后链表的末尾；如果list2还有剩余节点，则同样将剩余节点连接到合并后链表的末尾。

最后返回head.next，即为合并后的链表。

## 三、提交结果 ##

![在这里插入图片描述][84b04a4924ed47ec89f8901b3d210531.png]

[e7a98dccf17d40069c931cf6dd8964c2.png]: https://img-blog.csdnimg.cn/e7a98dccf17d40069c931cf6dd8964c2.png
[84b04a4924ed47ec89f8901b3d210531.png]: https://img-blog.csdnimg.cn/84b04a4924ed47ec89f8901b3d210531.png

发表评论取消回复

表情：

评论列表（有 0 条评论，28人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode题：21合并两个有序链表

21合并两个有序链表题目描述 > 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 > > 示例 1： > >

短命女/ 2024年02月20日 13:13/ 0 赞/ 197 阅读

相关【Leetcode刷题】算法：合并两个有序链表

文章目录一、题目介绍二、解决办法三、提交结果一、题目介绍 ![在这里插入图片描述][e7a98dccf17d40069c931cf6dd

约定不等于承诺〃/ 2023年10月10日 18:58/ 0 赞/ 29 阅读

相关 [leetcode] 合并两个有序链表

题目将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1->2->4, 1->3->4 输

柔光的暖阳◎/ 2023年06月13日 09:51/ 0 赞/ 10 阅读

相关 leetcode算法题--合并两个有序链表

题目概述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

末蓝、/ 2022年11月26日 01:44/ 0 赞/ 186 阅读

相关 leetcode-合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1：输入：l1 = [1,2,4], l

╰半橙微兮°/ 2022年09月12日 14:57/ 0 赞/ 226 阅读

相关 LeetCode 合并两个有序链表

1 题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ![在这里插入图片描述][watermark_type

以你之姓@/ 2022年09月11日 15:28/ 0 赞/ 261 阅读

相关 Leetcode 合并两个有序链表

问题描述 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3

约定不等于承诺〃/ 2022年03月16日 00:42/ 0 赞/ 296 阅读

相关 LeetCode(合并两个有序链表)

题目将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1->2->4, 1->3->4 输出：1->1-

ゝ一世哀愁。/ 2022年02月03日 13:27/ 0 赞/ 317 阅读

相关【LeetCode】合并两个有序链表

Java code class Solution { public ListNode mergeTwoLists(ListNod

以你之姓@/ 2021年11月01日 16:22/ 0 赞/ 354 阅读

相关 [LeetCode]简单题-合并两个有序链表

> [21. 合并两个有序链表][21.] 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。输入：1->2->4, 1->3->4

分手后的思念是犯贱/ 2021年09月19日 23:34/ 0 赞/ 283 阅读