21. 合并两个有序链表

Difficulty

easy

Tags

链表

URL

https://leetcode-cn.com/problems/merge-two-sorted-lists/

Star

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

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

通过次数585,985提交次数886,627

法1 迭代

思路

先新建一个临时头节点demmy，再建一个尾指针tail指向demmy（tail = demmy）

然后比较两链表的头指针大小，令tail始终指向小的那一个节点

当L1和L2两节点有一个为空时，则令tail指向不空的节点

返回demmy.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:
        demmy = ListNode(0)
        tail = demmy
        # 两个节点都不为空
        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        # 有一个为空，将非空的节点接到tail上
        tail.next = l1 if l1 else l2
        return demmy.next

法2 递归法

思路

先确定基线条件：有一个列表为空的时候


if l2 is None:
		return l1
if l1 is None:
		return 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:
        # 有一个为空，那么返回非空的链表
        if l1 is None or l2 is None:
            return l1 if l2 is None else l2
        # 判断较小的节点，将之后的节点合并，并返回该节点
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2