题目描述
思路解析动画文字版
记住这一句:切组的长度是 1,2,3,4 一路递增,但真正决定反不反转的,是每一组实际分到几个节点,偶数就翻、奇数就留。下面从第一个节点开始,一组一组走。
总览 · 8 个节点等待切组：先看这条链表,从左到右 8 个节点,值分别是 5,2,6,3,9,1,7,3,末尾的 null 表示到头了。开始之前先约定两个记号:i 表示当前这一组从哪个位置起,现在是 0;size 表示当前这一组的目标长度,从 1 起步。接下来每处理完一组,size 就加 1,i 跳到下一组的开头。
按 1,2,3,4 切组 · 最后一组分到 2 个：先在脑子里把组划出来。第一个节点 5 自己是第一组,长度 1;接着 2 和 6 是第二组,长度 2;再接着 3,9,1 是第三组,长度 3;第四组本该要 4 个,可后面只剩 7 和 3 两个节点了,那就分到 2 个,长度 2。所以四组的长度是 1,2,3,2。注意最后一组被截短了,它的长度要按实际分到的算。
第一组开始 · 目标长度 size=1,从位置 0 起：轮到第一组。当前 i=0,这一组的目标长度 size=1。组头先落在位置 0 的节点 5 上。接下来要从这里往后数,看这一组实际能分到几个节点。
第一组测长 · 实际长度=1：从位置 0 往后数 1 个,组尾停在位置 0 的节点 5。这一组的实际长度就是 1,正好等于目标长度。
第一组结算 · 长度 1 是奇数,原样保留：这一组的实际长度是 1,奇数。规则是奇数组一个都不动,原样保留。于是把这 1 个节点直接定下来,标成已完成。第一组只有一个节点,天然没法反转,也符合规则。下面 size 加 1,i 跳到位置 1,处理下一组。
第二组开始 · 目标长度 size=2,从位置 1 起：轮到第二组。当前 i=1,这一组的目标长度 size=2。组头先落在位置 1 的节点 2 上。接下来要从这里往后数,看这一组实际能分到几个节点。
第二组测长 · 实际长度=2：从位置 1 往后数 2 个,组尾停在位置 2 的节点 6。这一组的实际长度就是 2,正好等于目标长度。
第二组反转准备 · 长度 2 是偶数,摆好 l 和 r：这一组的实际长度是 2,偶数,要反转。反转的办法很直接:左指针 l 指组头位置 1,右指针 r 指组尾位置 2,把 l 和 r 的值交换,然后 l 右移、r 左移,一直到它们相遇或错过。这一组只有两个节点,交换一次就完事。
第二组交换第 1 对 · 位置 1 与 2：把位置 1 和位置 2 两个节点的值交换。交换以后,位置 1 变成 6,位置 2 变成 2。接着 l 往右、r 往左一走就相遇了,这一组的反转到此结束。
第二组结算 · 反转完成,值序变为 6,2：这一组反转完毕。反转前这一段的值是 2,6,反转后变成 6,2。把这 2 个节点定下来,标成已完成。下面 size 加 1,i 跳到位置 3,接着往后处理。
第三组开始 · 目标长度 size=3,从位置 3 起：轮到第三组。当前 i=3,这一组的目标长度 size=3。组头先落在位置 3 的节点 3 上。接下来要从这里往后数,看这一组实际能分到几个节点。
第三组测长 · 实际长度=3：从位置 3 往后数 3 个,组尾停在位置 5 的节点 1。这一组的实际长度就是 3,正好等于目标长度。
第三组结算 · 长度 3 是奇数,原样保留：这一组的实际长度是 3,奇数。规则是奇数组一个都不动,原样保留。于是把这 3 个节点直接定下来,标成已完成。值和顺序都不变。下面 size 加 1,i 跳到位置 6,处理下一组。
第四组开始 · 目标长度 size=4,从位置 6 起：轮到第四组。当前 i=6,这一组的目标长度 size=4。组头先落在位置 6 的节点 7 上。接下来要从这里往后数,看这一组实际能分到几个节点。
第四组测长 · 实际长度=2(不足 size,被截短)：从位置 6 往后数,本想数够 4 个,可到 7 就是最后一个节点了,后面没有了。这一组实际只分到 2 个,组尾停在位置 7。这就是最后一组被截短的情形,它的实际长度是 2,而不是目标的 4。
强调 · 判奇偶看实际长度 2,不是目标 4：这里是最容易出错的一步。这一组目标长度 size 是 4,是偶数;但它实际只分到 2 个节点。到底反不反转,要看实际长度 2 的奇偶,而不是看目标 4。实际长度 2 是偶数,所以它照样要反转。本例目标 4 和实际 2 恰好同为偶数,判断碰巧一致;可要是最后一组实际分到 3 个,3 是奇数就不该反转,这时还拿目标 4 去判反而会把该留的翻了。所以判奇偶永远认实际长度。
第四组反转准备 · 长度 2 是偶数,摆好 l 和 r：这一组的实际长度是 2,偶数,要反转。反转的办法很直接:左指针 l 指组头位置 6,右指针 r 指组尾位置 7,把 l 和 r 的值交换,然后 l 右移、r 左移,一直到它们相遇或错过。这一组只有两个节点,交换一次就完事。
第四组交换第 1 对 · 位置 6 与 7：把位置 6 和位置 7 两个节点的值交换。交换以后,位置 6 变成 3,位置 7 变成 7。接着 l 往右、r 往左一走就相遇了,这一组的反转到此结束。
第四组结算 · 反转完成,值序变为 3,7：这一组反转完毕。反转前这一段的值是 7,3,反转后变成 3,7。把这 2 个节点定下来,标成已完成。下面 size 加 1,i 跳到位置 8,接着往后处理。
全部处理完 · 最终链表 5,6,2,3,9,1,3,7：四组全部处理完了。第一组长度 1 奇数没动;第二组长度 2 偶数,5 后面的 2,6 翻成 6,2;第三组长度 3 奇数没动;最后一组长度 2 偶数,7,3 翻成 3,7。整条链表最终是 5,6,2,3,9,1,3,7,这就是答案。
回放 · 哪些组翻了,哪些没翻：再回放一遍。判断反不反转,自始至终只看一条:这一组实际分到的节点个数是奇是偶。第一组 1 个、第三组 3 个,都是奇数,原样保留;第二组 2 个、第四组 2 个,都是偶数,组内反转。特别记住最后一组:它目标是 4 个,实际只分到 2 个,按实际长度 2 是偶数,照样要翻。
边界想清:单节点原样;[1,2] 第二组只分到一个是奇数不翻;[1,2,3,4] 只有中间那两个偶数组被反转。
面试重点:按自然数长度切组、判奇偶用实际长度、抄值重建 O(n) 空间但好写、原地翻指针能省到 O(1) 空间。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]: vals = [] cur = head while cur: vals.append(cur.val) cur = cur.next i, size = 0, 1 while i < len(vals): j = min(len(vals), i + size) if (j - i) % 2 == 0: vals[i:j] = reversed(vals[i:j]) i = j size += 1 dummy = ListNode(0) cur = dummy for v in vals: cur.next = ListNode(v) cur = cur.next return dummy.next复杂度
- 时间：O(n)，n 是链表节点数。抄值一遍 O(n);切组反转阶段,每个节点在它所属的偶数组里最多被交换一次,所有组的长度加起来就是 n,总反转工作量 O(n);重建链表再一遍 O(n)。合起来随节点数线性增长
- 空间：O(n)，按峰值算。参考解额外开了一个长度为 n 的值数组存所有节点值,这是主要开销,所以是 O(n)。若改成在链表上原地翻指针,可以做到 O(1),但参考解走的是抄值重建这条更好写的路
易错点
面试追问把动画讲成自己的话
追问这题的核心处理是什么?
追问为什么判奇偶要用实际长度而不是目标长度?
追问抄值重建和链表原地翻指针,复杂度差别在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
删除链表的中间节点
LeetCode 2095 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题