LeetCode 题解工作台
合并两个链表
给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。 请你将 list1 中下标从 a 到 b 的全部节点都删除，并将 list2 接在被删除节点的位置。 下图中蓝色边和节点展示了操作后的结果： 请你返回结果链表的头指针。 示例 1： 输入： list1 = [10,…
1
题型
6
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
直接模拟题目中的操作即可。 在实现上，我们使用两个指针 和 ，初始时均指向链表 `list1` 的头节点。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。
请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果：
请你返回结果链表的头指针。
示例 1：
输入：list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002] 输出：[10,1,13,1000000,1000001,1000002,5] 解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
示例 2：
输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004] 输出：[0,1,1000000,1000001,1000002,1000003,1000004,6] 解释：上图中蓝色的边和节点为答案链表。
提示：
3 <= list1.length <= 1041 <= a <= b < list1.length - 11 <= list2.length <= 104
解题思路
方法一：模拟
直接模拟题目中的操作即可。
在实现上，我们使用两个指针 和 ，初始时均指向链表 list1 的头节点。
然后我们向后移动指针 和 ，直到指针 指向链表 list1 中第 个节点的前一个节点，指针 指向链表 list1 中第 个节点。此时我们将 的 next 指针指向链表 list2 的头节点，将链表 list2 的尾节点的 next 指针指向 的 next 指针指向的节点，即可完成题目要求。
时间复杂度 ，空间复杂度 。其中 和 分别为链表 list1 和 list2 的长度。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeInBetween(
self, list1: ListNode, a: int, b: int, list2: ListNode
) -> ListNode:
p = q = list1
for _ in range(a - 1):
p = p.next
for _ in range(b):
q = q.next
p.next = list2
while p.next:
p = p.next
p.next = q.next
q.next = None
return list1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + m) since both lists are traversed once; space complexity is O(1) because the merge uses in-place pointer adjustments without extra structures. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Watches for correct identification of pre-a and post-b nodes.
- question_mark
Checks for in-place pointer updates without creating new nodes unnecessarily.
- question_mark
Confirms understanding of linked-list edge cases and index handling.
常见陷阱
外企场景- error
Failing to connect the last node of list2 to the node after b.
- error
Incorrectly calculating indices a and b, leading to wrong nodes removal.
- error
Accidentally creating cycles or losing part of list1 during pointer reassignment.
进阶变体
外企场景- arrow_right_alt
Merge multiple segments from list1 with different lists in sequence.
- arrow_right_alt
Perform the merge in a circular linked list scenario.
- arrow_right_alt
Merge with additional constraints like preserving a sorted order.