leetcode-21:合并两个有序链表

简介: leetcode-21:合并两个有序链表

题目

题目链接

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

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

解题

方法一:递归

# 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, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

方法二:迭代

创建一个新的节点,将两个链表的节点依次比较,小的则加入到新的链表后。最后l1和l2至少有一个是空了,那么把不空的l1或l2,全部添加在新链表后面就行了。

# 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:
        dummy = ListNode()
        cur = dummy
        while l1 and l2:
            if l1.val<=l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 is not None else l2
        return dummy.next

另外一种写法

# 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:
        dummy = curr = ListNode()
        while l1 or l2:
            if not l1:
                curr.next = l2
                break
            if not l2:
                curr.next = l1
                break
            if l1.val<l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        return dummy.next
相关文章
|
26天前
|
索引 Python
【Leetcode刷题Python】328. 奇偶链表
在不使用额外空间的情况下,将链表中的奇数和偶数索引节点重新排序的方法,并提供了相应的Python实现代码。
24 0
|
26天前
|
Python
【Leetcode刷题Python】25.K 个一组翻转链表
解决LeetCode "K 个一组翻转链表" 问题的三种方法:使用栈、尾插法和虚拟节点顺序法,并提供了每种方法的Python实现代码。
25 0
|
15天前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
15天前
|
存储 算法
LeetCode第86题分隔链表
文章介绍了LeetCode第86题"分隔链表"的解法,通过创建两个新链表分别存储小于和大于等于给定值x的节点,然后合并这两个链表来解决问题,提供了一种简单易懂且操作原链表的解决方案。
LeetCode第86题分隔链表
|
15天前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
15天前
|
算法
LeetCode第23题合并 K 个升序链表
这篇文章介绍了LeetCode第23题"合并K个升序链表"的解题方法,使用分而治之的思想,通过递归合并链表的方式解决了这个难题。
LeetCode第23题合并 K 个升序链表
|
25天前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
18 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
3天前
|
C++ 索引
leetcode 707.设计链表
本文提供了解决LeetCode 707题"设计链表"的C++实现,包括单链表的节点定义和类方法实现,如添加节点、获取节点值、删除节点等。
|
15天前
|
算法
LeetCode第92题反转链表 II
文章分享了LeetCode第92题"反转链表 II"的解法,通过使用四个指针来记录和更新反转链表段的头部、尾部以及前一个和后一个节点,提供了一种清晰且易于理解的解决方案。
LeetCode第92题反转链表 II
|
15天前
|
算法
LeetCode第21题合并两个有序链表
该文章介绍了 LeetCode 第 21 题合并两个有序链表的解法,通过创建新链表,依次比较两个链表的头节点值,将较小的值插入新链表,直至其中一个链表遍历完,再将另一个链表剩余部分接到新链表后面,实现合并。
LeetCode第21题合并两个有序链表