How do I efficiently merge two sorted linked lists?

Use linked-list pointer manipulation, iterating through both lists and selecting the smaller node at each step, or apply recursion to merge them.

What is the time complexity of merging two sorted linked lists?

The time complexity is O(n + m), where n and m are the lengths of the two lists being merged.

Is recursion or iteration better for merging two sorted lists?

Both approaches have O(n + m) time complexity, but recursion uses additional space for the call stack, whereas iteration can be more space-efficient.

Can the iterative solution handle empty lists?

Yes, the iterative solution can handle empty lists by checking for null pointers before performing comparisons.

What happens if the lists have different lengths?

The algorithm continues comparing the remaining nodes of the longer list after one list is exhausted, efficiently merging the remaining nodes.

#21

Easy

auto_awesome链表指针操作

LeetCode 题解工作台

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1：输入： l1 = [1,2,4], l2 = [1,3,4] 输出： [1,1,2,3,4,4] 示例 2：输入： l1 = [], l2 = [] 输出： [] 示例 3：输入： 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 均按 非递减顺序 排列

lightbulb

解题思路

方法一：递归

我们先判断链表 $l_1$ 和 $l_2$ 是否为空，若其中一个为空，则返回另一个链表。否则，我们比较 $l_1$ 和 $l_2$ 的头节点：

若 $l_1$ 的头节点的值小于等于 $l_2$ 的头节点的值，则递归调用函数 $mergeTwoLists(l_1.next, l_2)$ ，并将 $l_1$ 的头节点与返回的链表头节点相连，返回 $l_1$ 的头节点。
否则，递归调用函数 $mergeTwoLists(l_1, l_2.next)$ ，并将 $l_2$ 的头节点与返回的链表头节点相连，返回 $l_2$ 的头节点。

时间复杂度 $O(m + n)$ ，空间复杂度 $O(m + n)$ 。其中 $m$ 和 $n$ 分别为两个链表的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# 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: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        if list1 is None or list2 is None:
            return list1 or list2
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of pointer manipulation and its impact on time and space complexity.
question_mark
Evaluate the candidate's grasp of recursion and how it compares to iteration in this context.
question_mark
Assess the candidate's ability to handle edge cases, such as empty lists or lists of different lengths.

warning

常见陷阱

外企场景

error
Failing to handle the case where one list is empty.
error
Incorrectly managing pointer updates when merging nodes.
error
Not optimizing for space by using an iterative approach when recursion could lead to stack overflow.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Merging more than two lists.
arrow_right_alt
Merging lists of different sizes while maintaining performance.
arrow_right_alt
Handling negative numbers or different data types in the nodes.

help

常见问题

外企场景

继续练习

#24 两两交换链表中的节点 #25 K 个一组翻转链表 #2 两数相加