题目描述
思路解析动画文字版
记住「先定位 prev 和 after 这两个端点,再把 list2 接在它们中间」,下面逐帧套它。关键是 after 必须先找好,别先断了链。
先看 list1:0→1→2→3→4→5→6。目标是把下标 2 到 5 这四个节点(值 2、3、4、5)删掉。
再看 list2:100→101。它要整条接进 list1 被删段留下的缺口里。
先把删除区间标出来:下标 a=2(值 2)到 b=5(值 5)这四个节点(灰色)要整段删掉。我们的目标就是找到它两侧的 prev 和 after,把 list2 嫁接进去。
找 prev:从 list1 头出发,要走 a-1 = 1 步。现在站在下标 0(值 0),还没动。
走 1 步,到下标 1(值 1)。它正好是被删段(下标 2 起)的前一个节点,这就是 prev。
把 prev 牢牢记住:稍后接线的第一刀就落在它身上(prev.next 要改指向 list2)。但先别动它,得先把 after 找到。
after 从 prev 出发数 b-a+2 = 5 步。第 1 步到下标 2(值 2),这是要删的第一个节点,标灰。
第 2 步到下标 3(值 3),仍在被删段里,继续标灰往后走。
第 3 步到下标 4(值 4),还是要删的节点。
第 4 步到下标 5(值 5),这是被删段的最后一个(b=5)。
第 5 步到下标 6(值 6)。它在被删段之外,是删完后第一个要保留的节点,这就是 after。为什么是 5 步:从 prev 跨过被删的 4 个节点、再多走 1 步落到它们后面,正好 b-a+2 步。
两个端点都拿到了:prev = 值 1、after = 值 6,中间灰色的 2、3、4、5 就是要旁路掉的整段。接下来动手接线。
第一刀:把 prev 原来指向值 2 的 next 断开(prev 和值 2 之间的箭头断掉)。值 2 这一段从此脱离主链,准备改接 list2。
接线①:prev.next = list2 头 100。现在主链变成 0→1→100→101…,list2 已经挂上(蓝色)。但 100→101 之后还是断的,缺口的后半截还没接回。
为了把 after 接回来,得先找到 list2 的尾节点。tail 从 list2 头 100 出发往后走。此刻 101 和 after(值 6)之间还是断的。
tail 走到 101,它的 next 还是空的(和 after 之间断着),说明 101 就是 list2 的尾节点。第二刀就落在它身上。
接线②:把 tail(101)的 next 指向 after(值 6),原本断开的箭头现在接上了。这样 list2 的尾就重新连回了 list1 保留的后半段。
101→6 接好了,两处接线都完成。从 list1 返回的头已经到不了 2、3、4、5,它们被主链旁路掉了。
最终链表:0→1→100→101→6,和预期一致。
回头看整趟:先走 a-1 步定位 prev、再走 b-a+2 步定位 after,然后两处接线(prev→list2 头、list2 尾→after)。全程只挪了几个指针、没开新链,额外空间 O(1)。
边界:a=1 则 prev 是头;list2 单节点尾即头;after 必然存在。
两个追问:无需先求长度;要返回被删段则先存头、断尾再接线。
参考代码
from typing import Optional, Listclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode: prev = list1 for _ in range(a - 1): prev = prev.next after = prev for _ in range(b - a + 2): after = after.next prev.next = list2 tail = list2 while tail.next: tail = tail.next tail.next = after return list1复杂度
- 时间：O(b + L2)，prev 走 a-1 步、after 再走 b-a+2 步(合计约 b 步),再走一遍 list2 找尾(长度 L2);与 list1 长度无关的剩余部分不用走
- 空间：O(1)，只用 prev、after、tail 几个指针,原地改链、不开新结构
易错点
面试追问把动画讲成自己的话
追问需要先数出 list1 的总长度吗?
追问如果还要求返回被删掉的那一段呢?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
交换链表中的节点
LeetCode 1721 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题