最近刷 LeetCode 61 旋转链表的时候我一度以为自己是老手稳赢不就是把链表后面 k 个节点搬到前面吗跟数组 rotate 一个套路。结果第一次提交空链表直接空指针第二次 k 传了 10 万我还在老老实实循环第三次更离谱返回的链表成环LeetCode 直接提示 cycle detected。这三连跪让我意识到旋转链表这题考的不是“会不会旋转”而是“有没有把链表的边界和取模想清楚”。这篇文章就从这三连跪开始把这道题的完整解法、边界陷阱和调试经验一次讲透适合刚入门链表题、或者刷了但总在边界挂科的读者。1. 先把“向右旋转 k 位”翻译成人话1.1 从数组旋转到链表旋转在数组里做旋转最简单的是利用切片或者两次反转arr[:] arr[-k:] arr[:-k]。链表不行你不能用下标访问任意位置也没法说“把第 n-k 个元素到末尾这一段切出来”。链表能做的只有一件事从头遍历然后改指针。所以旋转链表的本质是找到链表中的分界点把分界点右边的一段接到整个链表前面。比如 1-2-3-4-5 向右旋转 2 位结果是 4-5-1-2-3。这里的分界点是节点 33 的 next 原本指向 4我们要让 3 的 next 变成 None让原链表尾节点 5 的 next 指向 1同时返回 4 作为新头。所有旋转操作最终都归结为一句话找对分界点改写必要的指针。这里有一个容易误解的点链表节点本身的位置在内存里没有动变的只是连接关系。旋转不是真正“搬运”了节点而是头尾引用变了遍历的起点变了。理解这一点之后你再看任何链表旋转、反转、重排的题思路都会清楚很多。再补充一个等价视角向右旋转 k 步等价于向左旋转 n-k 步n 是链表长度。不过实现时与其纠结往左还是往右不如直接认准一个结论旋转后的新头节点是原链表正数第 n-k1 个节点新尾节点是正数第 n-k 个节点。这个结论是后面所有解法的地基。1.2 取模这道题真正的第一行代码k 的取值范围是非负整数也就是说 k 可能是 0也可能是 100000还可能比链表长度大得多。链表长度为 n每旋转 n 次链表就恢复原样所以真正有效的移动次数是 k % n。举个例子1-2-3k4。暴力模拟一下右移 1 次是 3-1-2右移 2 次是 2-3-1右移 3 次是 1-2-3右移 4 次是 3-1-2。结果等价于 k1。所以 4 % 3 1直接旋转 1 位就好。你看先取模能省掉大量无效操作。再列一个对照表直观感受一下链表长度 nkk % n实际效果500不变522正常旋转 2 位550不变572等价于旋转 2 位51000不变k % n 之所以重要不只是省时间。如果你不取模后面用快慢指针时 fast 要先走 k 步k 为 10 万而链表只有 3 个节点fast 早就走过头了。你可以写成让 fast 绕圈走但绕圈容易把自己绕晕不如老老实实先求长度再取模。链表求长度本来就需要 O(n) 遍历既然都遍历了顺手把尾节点也找到一点也不亏。还有一个很多人会漏的点取模之后 k 可能变成 0比如 k 正好等于 n 或 k 是 n 的整数倍。这时候旋转结果就是原链表直接返回 head。这个判断很重要因为后面所有找断点的逻辑都依赖 k 是小于 n 的正整数。k 为 0 时某些写法会算出负数步数一执行就出错。2. 成环断链最不容易写错的解法2.1 思路只有三步看到“旋转链表”这题我第一反应是“找到倒数第 k 个节点的前一个节点”然后改指针。但直接找断点容易因为步数算错而崩。更稳的写法是“先成环再断链”只需要三个步骤遍历链表数出长度 length同时记住尾节点 tail。把 tail.next 指向 head链表变成环形。根据取模后的 k从 head 开始走 length-k 步找到新的尾节点它的下一个节点就是新头然后把新的尾节点指向 None断开环。为什么成环之后再断链不容易错因为成环之后你不需要同时维护“头”和“尾”两个引用只需要在一个环上找到正确的断点剪一刀就行。打个比方你有一根绳子与其纠结从哪头数起不如先把头尾接成一个圈然后在想要的长度处剪开一定不会把方向搞反。这个类比同样适用于后面你会遇到的环形链表题目。用具体的链表 1-2-3-4-5k2 来跑一遍长度 length5取模后 k2尾节点 5 的 next 指向 1链表变成 1-2-3-4-5-1 的环。接着从 head 开始走 length-k-12 步到达节点 3。节点 3 就是新尾节点 4 是新头。把 3 的 next 置为 None返回 4得到 4-5-1-2-3。整个过程清晰明了。2.2 Python 完整实现这是我最终提交的版本注释写在代码里class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def rotateRight(head: ListNode, k: int) - ListNode: # 空链表、单节点、移动 0 次都不用处理 if not head or not head.next or k 0: return head # 1. 数长度顺带把尾节点找到 length 1 tail head while tail.next: tail tail.next length 1 # 2. 取模去掉整圈的无效旋转 k % length if k 0: return head # 3. 成环 tail.next head # 4. 找到新尾节点从 head 走 length - k - 1 步 new_tail head for _ in range(length - k - 1): new_tail new_tail.next new_head new_tail.next # 新尾节点的下一个就是新头 new_tail.next None # 断开环 return new_head代码不长核心就两个细节一是先取模再判断 k 0能避免成环后再恢复原状的麻烦二是最后断开时先保存 new_head 再置空 new_tail.next顺序不能反。如果你先执行new_tail.next None再想拿new_tail.next就成了空指针经典的“先拆桥再回头找路”错误。时间复杂度 O(n)空间复杂度 O(1)。链表题的优势就是不需要额外数组原地改指针就行。2.3 断点计算为什么是 length - k - 1 步这是整道题最容易被绕晕的地方值得单独说清楚。假设链表 1-2-3-4-5k2len5。旋转后的新头是 4新尾是 3。新尾在链表里的位置从 1 开始编号是第 len-k 3 个节点数一下1、2、3确实数到 3。而从 head 出发要走到节点 3需要走 2 步head 到 2 是第 1 步2 到 3 是第 2 步。所以循环次数不是 len-k而是 len-k-1。“位置编号”和“移动步数”之间永远差 1这是链表题里最经典的陷阱。我自己的习惯是不要背公式一律按“从当前节点出发需要走几步才能到目标节点”来算。每次写循环前心里默念一遍“头节点已经算走了 0 步”可以有效减少粗心错误。如果你还是不放心就在本地打印一下每一步到达的节点值。很多题目不是你不会写而是算错一步之后跟着错误代码调试越调越懵。打印大法虽然朴素但真的管用。3. 边界条件全是坑我在提交记录里翻出的教训3.1 空链表和单节点不加这行一定报错LeetCode 的测试用例里一定有[]和[1]而且 k 可能给一个很大的值比如 k99。如果 head 为 None代码访问head.next会直接 AttributeError程序当场崩掉。如果只有单节点成环也能转但没必要。所以函数第一行统一处理三种情况not head、not head.next、k 0。注意k 0在这里处理是一种快捷方式但就算第一行没写取模之后也必须再写一次。为什么因为即使 k 不是 0取模后也可能变成 0。我见过有人只在前面对k 0做了判断结果 klength 时照样走进成环逻辑计算出负数步数返回一堆莫名其妙的链表。我的建议是第一行的k 0可以理解为“提前退出的优化”取模后的if k 0: return head才是真正的正确性保障。两道闸门都装上才睡得安稳。3.2 k 是链表长度的倍数[1,2,3,4,5]k5旋转 5 次等于没转应该原样返回 [1,2,3,4,5]。k10、15 同理。写成代码就是取模之后判断if k % length 0: return head。如果不加这个判断会怎样取模后 k0length-k-1 等于 -1range(-1)不会进入循环new_tail 仍然是 head。接着new_head new_tail.next也就是 head.next然后new_tail.next None这等于把链表从第 2 个节点处切断只剩一个节点。结果完全错误。所以“取模后 k 为 0 必须提前返回”不是优化是必须有的分支。还有一种隐蔽情况链表只有两个节点比如 [1,2]k1。length2取模后 k1length-k-10不需要移动new_tail 就是 head。new_head 是 head.next也就是节点 2。然后把节点 1 的 next 置空把原尾节点节点 2 的 next 指向 head得到 2-1。这里每一步都对但很容易因为“循环次数为 0”而产生自我怀疑。记住循环次数为 0 不代表逻辑错它表示目标节点就是起点。3.3 成环后忘记断开本地测试不容易发现如果你把 tail.next 改成 head 之后忘记在返回值里把 new_tail.next 置为 NoneLeetCode 后台会检测到环报 “cycle detected”。这种错误很恶心因为本地如果只打印一遍节点值你会看到 4-5-1-2-3-1-2-3...由于已经出现过 1程序如果不做保护就会死循环。怎么快速定位是不是带环我写本地测试时会专门在链表打印函数里加一个 id 集合把访问过的节点对象记录起来如果走到重复节点立刻停止并标记 Cycle。这个方法对所有链表题都有用尤其是做环形链表相关题目时几乎是必备工具。另一个经验是修改指针前先在心里画一下最终形态。比如成环法最后一定是“一条直线链表”新尾节点的 next 必须为 None。如果最终形态应该是直线但代码某处还在引用旧节点多半就是断链位置找错了。3.4 本地调试模板造链表、打印链表在网页编辑器里调试链表题很痛苦所以我习惯在本地把输入、输出完整跑一遍重点看指针变化。三个小函数就能搭一个顺手的环境数组转链表、链表转字符串带防环、main 里跑多组用例。def build_linked_list(arr): dummy ListNode(0) cur dummy for val in arr: cur.next ListNode(val) cur cur.next return dummy.next def linked_list_to_str(head): res [] seen set() cur head while cur: if id(cur) in seen: res.append(Cycle?) break seen.add(id(cur)) res.append(str(cur.val)) cur cur.next res.append(NULL) return - .join(res) if __name__ __main__: cases [([1,2,3,4,5], 2), ([1,2,3], 4), ([1], 99), ([], 0)] for arr, k in cases: head build_linked_list(arr) new_head rotateRight(head, k) print(farr{arr}, k{k} {linked_list_to_str(new_head)})这段代码会输出arr[1,2,3,4,5], k2 4 - 5 - 1 - 2 - 3 - NULL arr[1,2,3], k4 2 - 3 - 1 - NULL arr[1], k99 1 - NULL arr[], k0 NULL我自己的习惯是每次提交前至少跑六组用例空链表、单节点、k0、k长度、k长度、正常情况。这套动作帮我挡下了很多低级错误也让我在面试手写代码时更自信。4. 换一种姿势快慢指针解法4.1 快慢指针的移动逻辑有些人不太喜欢成环法觉得“把链表改成环”听起来有点暴力。那可以试试快慢指针不直接改环而是找到正确的断点再改指针。快慢指针的思路分四步仍然先遍历求 length 和 tail做k % length。让 fast 指针先向前走 k 步。slow 停在 head之后 slow 和 fast 一起移动直到 fast.next 为 None 时停止。此时 fast 是原链表尾节点slow 恰好是新尾节点slow.next 是新头。为什么 slow 最后会停在新尾节点上因为 fast 和 slow 之间始终隔着 k 个节点。fast 走到整个链表的最后一个节点时它距离终点已经不能继续前进而此时 slow 距离 fast 还有 k 个身位等价于 slow 距离链表末尾 k 步。从链表末尾倒数 k 个节点正好就是旋转 k 次之后的新尾节点。这里有点绕但拿着链表实际走一遍就明白了。用 1-2-3-4-5k2 来模拟fast 先走 2 步到节点 3然后 slow 在节点 1fast 和 slow 一起走。fast 从 3 走到 4slow 从 1 走到 2。fast 从 4 走到 5slow 从 2 走到 3。此时 fast.next 为 None停止。slow 在节点 3正是新尾节点。4.2 代码与成环法的对照def rotateRight_two_pointer(head: ListNode, k: int) - ListNode: if not head or not head.next or k 0: return head length 1 tail head while tail.next: tail tail.next length 1 k % length if k 0: return head fast head for _ in range(k): fast fast.next slow head while fast.next: slow slow.next fast fast.next new_head slow.next slow.next None fast.next head return new_head这段代码和成环法本质一模一样都是先求出 length再定位“从头部数第 length-k 个节点”。区别只是定位方式不同。成环法用for _ in range(length-k-1)直接走到新尾节点快慢指针用 fast 先走 k 步来拉开一个固定距离再让 slow 慢慢追上。时间复杂度都是 O(n)空间都是 O(1)。用表格对照一下对比项成环断链法快慢指针法核心操作尾节点指向头节点再找断点剪开快指针先走 k 步拉出距离再同步走代码量更短稍长找新尾的方式按步数直接走靠快慢指针距离定位可迁移性一般能迁移到删除倒数第 N 个节点4.3 两种解法的取舍我个人的建议是优先掌握成环断链法因为代码短、逻辑直白面试时不容易在指针操作上卡壳。快慢指针解法可以作为补充因为它的思想可以迁移到 LeetCode 19 删除倒数第 N 个节点这类题。两个解法都有一个共同前置步骤求长度、取模。这也是旋转链表和“倒数第 k 个节点”题目的最大区别其他题 k 天然小于等于长度旋转链表里 k 可能任意大必须先取模。另外提醒一句快慢指针法在k % length 0时同样要提前返回。如果不返回fast 先走 0 步slow 和 fast 同步走最后 slow 会停在链表末尾切出的结果就是错的。边界判断永远是第一位的不管选哪种解法都不能省。5. 一题带出一串链表题的通用方法论5.1 链表题的三个基本功旋转链表做完之后我复盘了一下发现它几乎把链表操作里的所有基本功都串起来了。第一遍历求长度、找尾节点。这是链表题最常用的前置操作。你做的很多题目第一步都是先从头走到尾数长度或者记住最后一个节点。和数组不同链表没有 len() 方法这个 O(n) 遍历躲不掉。既然躲不掉就把它当成常规操作。第二指针步数计算。位置编号和移动步数之间差 1这个坑我前面专门讲过了。很多链表题的隐蔽 bug 都来自这里比如“走到第 3 个节点”和“走 3 步到达的节点”根本不是一回事。我自己的方法是把所有类似逻辑都统一成“需要走几步”代码读起来也更直白。第三断链和成环。很多“变形”题都是在这两种状态之间切换视角。比如环形链表检测141、环形链表 II142核心就是判断环和找环入口。旋转链表则是显式地把链表首尾相接再剪开和环形链路题是同一类底层思维。5.2 用这张清单避坑我在本地调试时准备了一张“链表题提交前检查清单”每次写完代码挨个过一遍检查项具体操作空链表输入 None确保函数第一行能返回单节点输入 [x]期望输出还是 [x]不能带环k0期望输出原链表klength期望输出原链表klength先取模再走指针不许直接走 k 步断链返回前确认新尾节点的 next 为 None保存引用修改 next 之前先保存要返回的 new_head这张表不局限在旋转链表上。任何涉及修改指针的链表题提交前都值得花 30 秒过一遍。尤其是“保存引用”这一项很多人写反转链表时丢引用就是因为在cur.next prev之前没有先用 next 临时变量保存原来的 cur.next。5.3 可以顺手刷掉的同类题如果你正按题号顺序刷到 61我非常建议一起刷这几道LeetCode 19删除链表的倒数第 N 个结点。快慢指针标准应用和 61 的定位逻辑几乎一样。LeetCode 24两两交换链表中的节点。练 dummy node 和指针翻转顺序。LeetCode 92反转链表 II。练“找到断点再局部反转”。LeetCode 141 / 142环形链表和环形链表 II。练环的判定和数学推导。LeetCode 23合并 K 个升序链表。练多指针和优先队列是链表的进阶综合题。我拿 LeetCode 19 给你做一个具体迁移。删除倒数第 N 个节点可以先让 fast 走 n 步再让 slow 和 fast 一起走等 fast 走到尾部时slow 正好停在要删除节点的前一个节点。这套逻辑和旋转链表里“让 slow 停在新的尾节点”几乎是同一个模板只是最后改指针的动作不同。所谓刷题手感就是在这类重复模式中建立起来的。如果你想把 61 吃得更透还可以事后想一想如果 k 很大但链表很短成环法是不是天然容错快慢指针法和成环法到底哪个更适合讲给面试官听我个人觉得面试时讲成环法最干脆先证明取模再说“首尾相连找断点剪开”三步说完手写 15 行以内非常符合面试节奏。最后说点我个人的经验。旋转链表我前后刷了三遍第一遍在边界上翻车第二遍在断链上翻车第三遍才形成了自己的固定套路先判空求长度取模成环找断点。这之后凡是遇到“第几个节点”“倒数第几个节点”的题我都会先把这三个基本步骤写出来再动手效率和正确率都高了不少。一个小技巧在纸上画一个 5 节点的链表把 k 分别取 1、2、4、5、6 跑一遍10 分钟就能把这道题彻底吃透。链表题说穿了就是连接关系的重新编排想明白这一点很多坑自然就绕开了。