在Leetcode刷题的过程中链表专题是绕不开的硬骨头而旋转链表这道题题号经常被记混有人记成107有人记成61几乎每次面试题库里都会出现。我第一次做这道题的时候脑子里第一时间蹦出来的思路是循环k次每次把尾部节点搬到头部结果一提交就被测试用例教做人了。今天这篇就把这道题从头到尾聊透包括暴力解是怎么一步步改进到最优解的以及那些藏在测试用例里的边界条件到底有多阴。1. 旋转链表到底在考什么题目拆解与常见误区1.1 题目本意向右移动k位不是想象中那么简单先把这个题的内容说清楚。题目给的是一个单链表的头节点head和一个整数k要求将链表每个节点向右移动k个位置返回新的头节点。举个例子链表 1 - 2 - 3 - 4 - 5k 2移动后变成 4 - 5 - 1 - 2 - 3。这里很多人的第一个误区就出现了。大家平时接触数组的右移比较多数组右移k位是每个元素整体向右挪末尾元素溢出后补到开头。链表虽然操作逻辑类似但链表没有索引这个概念你没法直接知道某个位置的节点是谁只能从头一步步遍历。所以链表右移的本质是找到新头节点和新尾节点然后重新拼接指针。我在实际刷题的时候发现一个有意思的现象很多人能把暴力解写对但问到有没有更好的办法就卡住了。原因是他们始终停留在模拟移动的层面没有意识到旋转操作本质上是链表结构的重排。这个认知一旦建立后面的最优解几乎就是水到渠成的事。1.2 链表操作的三个基本功长度、取模、指针顺序说实话这道题的代码量很小核心解法在20行以内就能写完。但它被归类为经典的原因在于它同时考察了三个基本功。一是链表长度的计算。很多人一上来就想着怎么移动却忘了必须先遍历一遍拿到长度n后面所有的操作都依赖这个n。链表不像数组有length属性必须手动数一遍这个动作虽然简单但遗漏的后果很严重。二是取模运算的敏感性。k可能比n大得多比如链表长度为3k 4你总不能真的做4次移动吧实际上右移4位等价于右移1位因为4 mod 3 1。忘了取模是这道题最常见的翻车原因而且这种错误在k小于链表长度的测试用例里根本暴露不出来特别阴。三是指针操作的顺序。断链、衔接、更新头尾指针这三步的顺序一旦出错链表就会断成两截或者形成环轻则答案错误重则死循环。我见过不少人在本地跑得好好的一提交就超时——不是算法问题而是代码进入了死循环链表成环之后遍历永远走不完。1.3 和相邻题目的横向对比把旋转链表和同专题的两道题放在一起看会更有感觉。一道是删除链表的倒数第N个节点一道是两两交换链表中的节点。前者考察的是快慢指针寻找倒数第N个位置旋转链表也需要类似定位倒数位置的能力后者考察的是指针重连的纪律性旋转链表断链后同样要求严格的重连顺序。可以说旋转链表是这两类能力的综合题。这也是为什么面试官特别喜欢拿它做基础能力摸底——代码量不大但该踩的坑一个不少。如果你能在15分钟内把这题写得干净利落同时把边界情况说清楚面试官基本可以确认你的链表基本功是过关的。2. 先写一版能跑的暴力解从直觉到边界暴露2.1 暴力解思路模拟每次移动拿到题目后最直觉的思路就是循环k次每次做一次尾节点搬到头部的操作。具体来说每一轮需要做的事是遍历链表找到尾节点tail和它的前驱节点prev让prev.next null把tail从原链表中摘下来让tail.next head把tail放到链表头部更新head tail这个思路在k很小的时候完全能跑通。比如链表 1 - 2 - 3k 1一轮操作后变成 3 - 1 - 2完全正确。我最初学链表操作的时候也是从这种最朴素的模拟开始练的它能帮你理清指针的指向关系。2.2 暴力解代码实现我用Python写一下这个版本方便展示思路def rotateRight(head, k): if not head or not head.next: return head for _ in range(k): # 找尾节点和前驱 prev None cur head while cur.next: prev cur cur cur.next # cur是尾节点prev是它的前驱 prev.next None cur.next head head cur return head代码很短逻辑看上去也没问题。但如果你真拿这个提交大概率会超时或者被极端用例卡住。很多人这时候会怀疑是自己的代码哪里写错了其实不是问题出在时间复杂度上。2.3 暴力解的两个致命问题时间和取模第一个致命问题是时间。每轮操作都要遍历整个链表找尾节点复杂度是O(kn)。如果k稍微大一点比如链表长度1万、k也是1万那就要执行1亿次遍历操作在Leetcode的测试用例下大概率超时。第二个致命问题是逻辑漏洞。当k大于链表长度n时循环k次虽然不会报错但做了大量无效的转圈操作。更严重的是如果k非常大比如10的9次方这个暴力解法根本不可能在限定时间内跑完。所以暴力解的价值不在于提交通过而在于帮我们建立一个基本认知每次移动都要遍历链表太浪费了。能不能只遍历一次或者只做一次切割就完成整个旋转带着这个问题最优解的思路就呼之欲出了。3. 最优解先成环再断链两步搞定3.1 核心观察右移k位等价于从倒数第k处断开这里有一个关键的数学观察。链表 1 - 2 - 3 - 4 - 5n 5k 2。右移2位的结果是 4 - 5 - 1 - 2 - 3。仔细对照原链表可以发现新链表其实就是从原链表的倒数第2个节点节点4处断开把后半段 4 - 5 挪到前半段 1 - 2 - 3 的前面。换句话说右移k位就是把链表从倒数第k个位置切开然后把后半段接到前半段前面。这个观察非常重要它把移动k次变成了一次切割时间复杂度从O(kn)降到了O(n)。我把这个观察写出来之后有读者问我为什么是倒数第k个而不是正数第n-k个这俩其实是一回事区别在于从哪个方向数。单链表只能从头往后走所以代码实现时你可能更需要正数第n-k个节点这个视角。但理解上从倒数第k个这个数学视角切入最直观。3.2 为什么先成环是最优雅的实现有了上面的观察实现方式有两个方向一个是先找到倒数第k个节点的位置断成两条链再接起来另一个是先把链表首尾相连成环再从正确的位置断开。我强烈推荐第二种成环的做法理由是它天然规避了断成两条链后处理空链表的各种边界分支。我把断成两截再拼接的代码写出来你对比一下就明白了def rotateRight(head, k): if not head or not head.next: return head n 1 cur head while cur.next: cur cur.next n 1 k k % n if k 0: return head # 找到新尾节点正数第 n-k 个节点 new_tail head for _ in range(n - k - 1): new_tail new_tail.next new_head new_tail.next new_tail.next None # 找到原尾节点接到head上 cur new_head while cur.next: cur cur.next cur.next head return new_head这段代码虽然也能跑但有个很尴尬的问题断开链表之后为了把后半段接到head上你还需要再次遍历找到原尾节点。也就是说它需要遍历链表两次半。而成环法只需要遍历一次在第一次遍历时就把尾节点记录下来了后面的断链操作完全不需要再找尾节点。另一个细节是断链法在new_tail.next None之后链表处于断开状态如果这中间有任何异常链表就丢了。成环法则始终有一条完整的环兜底操作起来更安全。所以我建议你直接记住成环法这个套路面试时写起来不仅快而且不容易出错。3.3 代码实现与逐行解释直接上Python代码def rotateRight(head, k): # 处理空链表和单节点链表的特殊情况 if not head or not head.next: return head # 第一步遍历链表计算长度n同时让尾节点指向head n 1 cur head while cur.next: cur cur.next n 1 # 此时cur是尾节点让尾节点指向头节点形成环 cur.next head # 第二步计算实际需要移动的步数取模 k k % n # 如果k 0说明不需要移动直接断开环返回原head if k 0: cur.next None return head # 第三步找到新链表的尾节点 # 新尾节点从头节点出发走 n - k - 1 步 new_tail head for _ in range(n - k - 1): new_tail new_tail.next # 第四步新头节点是新尾节点的下一个节点 new_head new_tail.next # 第五步断开环 new_tail.next None return new_head这里有个细节想单独拎出来说为什么第3步要走 n - k - 1 步因为成环后从头节点出发走 n - k 步会到达新头节点那么走 n - k - 1 步到达的自然就是新头节点的前一个节点也就是新尾节点。举个例子n 5k 2n - k - 1 2。从节点1出发走2步到节点3。新链表是 4 - 5 - 1 - 2 - 3尾节点确实是3。算得刚刚好。提示这里最容易出错的地方是步数多算一步或少算一步。我的记忆技巧是先想清楚新头节点在哪里再往前退一个就是新尾节点。你只要把n - k这一步记牢n - k - 1就不会错。3.4 Java版本参考如果面试官现场让你用Java写思路完全一致只是语法不同public ListNode rotateRight(ListNode head, int k) { if (head null || head.next null) { return head; } ListNode cur head; int n 1; while (cur.next ! null) { cur cur.next; n; } cur.next head; k k % n; if (k 0) { cur.next null; return head; } ListNode newTail head; for (int i 0; i n - k - 1; i) { newTail newTail.next; } ListNode newHead newTail.next; newTail.next null; return newHead; }核心逻辑一行都没变。这道题用Python和Java写出来的差异非常小说明算法本身足够简洁语言层面的干扰因素很少。如果你平时用C写也是同样的套路只是内存管理上要注意别让环残留导致内存泄漏虽然Leetcode不查这个但面试时最好提一嘴。4. 边界条件与隐藏的坑k的大小、链表长度、特殊情况4.1 空链表和单节点链表这两个是最容易漏掉的条件。很多人在写第一版代码时根本没判断结果运行时空指针异常。实际上这两行的作用是if not head空链表无法遍历直接返回if not head.next单节点链表无论k是多少旋转后还是它自己直接返回别看这两行简单它们能帮你省掉后面几乎所有的特判逻辑。有个取巧的写法是直接合并写成if not head or not head.next我用了一年多没有任何问题。面试时这么写不仅代码短还能让面试官觉得你考虑到了边界情况。4.2 k等于0的情况如果k 0按定义无需移动直接返回head。但注意如果你用的是成环法此时链表已经被连成环了必须手动断开否则返回的是一个带环的链表后面遍历会死循环。我在3.3节的代码里专门写了cur.next None这一步就是为了把环解开。这个问题特别隐蔽因为单独测k 0的用例时如果没有仔细检查返回链表的结构代码可能不会报错但放在复杂用例里就会导致诡异的内存问题。我刚开始刷题时就栽过一次本地测试k 0输出看起来正常但一提交就报错排查了半天才发现是返回的链表后面带着一个环。所以记住成环法里只要执行过成环操作返回之前一定要确认环已经断开。4.3 k大于链表长度的处理取模是必须的k 7n 5右移7位等价于右移2位因为 7 mod 5 2。记住这个结论不要想当然地以为多绕几圈也没关系在大数据量下多绕几圈就是超时。取模操作的位置也有讲究。可以在成环之前做也可以在成环之后做。我习惯放在成环之后因为这样代码读起来是先处理链表结构再处理数学逻辑语义更清晰。不过说实话这两种放法结果完全一样你只要记得做取模就行。注意k可能远大于n比如k 10^9n 3。如果不取模哪怕你的解法是O(n)也会因为多绕了很多圈而超时或者做无用功。取模这一步能把所有转圈操作压缩到至多n-1次。4.4 k恰为n的整数倍这个也是取模的衍生情况。如果k % n 0说明旋转了一圈又回到原点链表顺序不变。此时不取模的话暴力解法会白白执行n次移动而最优解法会在取模后得到k 0直接返回原链表省了一整轮无意义的操作。我建议在取模之后加一个判断如果k 0就提前返回。这样写虽然多了一行代码但逻辑分支清晰而且能避免后面找新尾节点时出现负数步数的问题。如果不加这个判断当k 0时n - k - 1 n - 1你会从头节点走n-1步走到原尾节点new_head则会指向原头节点结果虽然也正确但白白多走了n-1步。能提前返回就提前返回这是写算法的好习惯。4.5 如果k是负数怎么办一个值得准备的话题虽然Leetcode原题约束k是非负整数但面试官有可能会追问如果k为负数呢。负数的处理思路是这样右移-k位等价于左移k位而在一个长度为n的环形结构上左移k位等价于右移n - k位。用一个公式概括就是当k 0时令k n - (-k % n)然后继续走正常流程。我建议在代码里加上这几行作为防御式编程if k 0: k n - (-k % n)这样不管输入是什么代码都能正确处理。虽然题目不要求但面试时主动提出这一点会让面试官觉得你考虑问题比较全面。我就在一次模拟面试里靠这个细节拿到了小小的加分。5. 复杂度分析与面试官真正想听的东西5.1 时间和空间复杂度最优解的时间复杂度是O(n)因为遍历链表计算长度用了O(n)找新尾节点又用了O(n - k)时间实际上也是O(n)的量级。空间复杂度是O(1)因为只用了几个指针变量没有额外申请与链表长度相关的存储空间。这里要注意很多人会误以为找新尾节点那步是O(k)这是不对的。虽然for循环写了n - k - 1次但n - k - 1的最大值不超过n所以是O(n)上限和k无关。另外值得说的是这个算法不需要额外数组存储节点不像数组旋转那样借助辅助空间。链表虽然不支持随机访问但它在空间上的优势恰好在这里体现出来你可以通过改指针完成旋转不用复制数据。面试时主动提这一点能显示出你对数据结构特性的理解。5.2 为什么不能继续优化到O(log n)这道题很经典的一个追问是暴力解法O(kn)你优化到了O(n)那还能不能继续优化到O(log n)答案是不能。因为单链表本身不支持跳跃访问你无论如何都必须遍历一遍拿长度、找位置时间复杂度下界是O(n)。如果你抬杠说可以用额外数组存指针然后用数组模拟跳跃访问那确实可以做到更低的遍历次数但空间复杂度会变成O(n)而且这本质上已经不是链表操作了。面试官问这个问题的潜台词是看你知不知道链表访问是顺序的这个本质约束。能答出这一点说明你不是在背题而是真的理解数据结构。5.3 与数组旋转的对比为什么思路完全不同数组旋转比如右移k位有一个经典的三次反转解法也是O(n)时间O(1)空间。这个解法依赖数组的随机访问能力你可以直接交换相距任意距离的两个元素。链表做不到这一点所以不能照搬三次反转的思路。链表旋转的成环断链更像是剪切粘贴而数组旋转更像是整体平移。我见过有人试图用三次反转链表来解这道题方向就偏了。反转链表本身需要O(n)时间做完3次就是O(n)时间复杂度没错但代码复杂度远超成环法而且在改指针时极易出错。除非面试官明确要求否则没必要走那条路。遇到这类问题时先想清楚数据结构本身的特性再决定用什么策略这才是高效解题的正确打开方式。5.4 面试表达的节奏建议如果你在面试中遇到这道题我建议按这样的节奏表达先抛出暴力解明确指出它的两个瓶颈重复遍历、k过大时退化严重然后自然过渡到右移k位本质上是从倒数第k个位置切断最后给出成环实现。整个过程不要太快重点体现在为什么从倒数第k个位置切断这一点上。面试官要听的不是代码而是你的思路推演过程。我见过太多候选人代码秒写但对为什么成环解释得磕磕绊绊这反而会扣印象分。我自己面试别人的时候最想知道的是候选人如何处理边界条件。如果你能在写代码之前先把空链表、单节点、k比n大、k是n的倍数这四种情况列出来面试官基本就会对你有个不错的印象。记住代码是第二位的思路清晰才是第一位的。6. 刷题实战中的几点经验测试用例、画图与常见错误6.1 设计一套完整的自测用例刷链表题最重要的是自测用例的覆盖面。我常用的测试集合是这样的测试场景输入链表k值期望输出空链表[]任意[]单节点[1]任意[1]常规小链表[1,2,3]1[3,1,2]k等于0[1,2,3]0[1,2,3]k等于链长[1,2,3]3[1,2,3]k大于链长[1,2,3]4[3,1,2]k是链长的倍数[1,2,3]6[1,2,3]把这些用例跑一遍基本能覆盖所有边界。特别强调一下k等于链长的用例很多人会忽略一旦忽略就测不出取模分支是否正确。我还会额外测一个k 1的用例因为k 1是最小有效移动如果这个用例都不对那说明基础逻辑就有问题。还有一个调试技巧把返回链表的长度打印出来如果长度不等于原链表长度说明链表在操作过程中丢节点了。这个方法不仅能用于这道题几乎所有链表题都能用。6.2 画图是解开链表题的钥匙很多人在做链表题时卡住原因不是代码能力而是脑子里的图没画对。我强烈建议在草稿纸上手动模拟一遍完整过程尤其是成环断链这两步。我自己做题时习惯用方框代表节点箭头代表指针每做一步操作就在图上涂改一次。旋转链表这道题画一遍图胜过你在脑海里空想十遍。拿链表 1 - 2 - 3 - 4 - 5k 2 为例成环后的逻辑是1 - 2 - 3 - 4 - 5 - 1环形成n 5k 2n - k - 1 2从头节点1走2步到节点3节点3作为新尾节点节点3.next是节点4节点4就是新头节点断开3.next得到 4 - 5 - 1 - 2 - 3这个过程画一遍就全通了。如果你觉得画图麻烦也可以用调试器逐步跟踪指针的值但效果远不如手画。因为手动画图时你的大脑会强制思考这个指针现在指向谁这个问题而调试器只会让你被动接受结果。6.3 最常见的三个实现错误根据我刷题和帮人review代码的经验这道题的高频错误集中在三个地方。第一个是忘记取模。这个错误在k小于链表长度时根本不会暴露所以自测时一定要专门准备一个大k的用例。我自己就吃过一次亏当时k 2链表长度是3碰巧k比n小代码能跑通我就以为没问题了。直到面试官追问k 4呢我才意识到取模的重要性。第二个是断环位置错误。很多人找到了新头节点但断链时误把新头节点的下一个节点给断开了导致链表少了一个节点。本质上是对新尾节点和新头节点的定位混淆。这里有个口诀新尾节点永远是最后一段的第n-k个节点它的next才是新头节点而我们要断开的是新尾节点和它next之间的指针。第三个是保存临时指针的顺序问题。在需要重连指针的场景中必须先保存待操作的节点引用再修改指针。比如在暴力解的循环里如果你先执行了prev.next None然后再想拿cur的引用时操作顺序不同会导致不同的结果。这个习惯需要在平时刷题时就刻意养成——每次修改指针之前先问自己这个节点的引用还有人需要吗需要就先存下来。6.4 扩展如果是双向链表或循环链表面试官可能还会追问变体如果是双向链表呢双向链表旋转的思路和单链表基本一致唯一的麻烦是每个节点除了next指针还有prev指针旋转后需要同时维护两条指针链。具体来说在断链时不仅要断开next方向还要把prev方向也处理干净否则会留下指向已经被移走节点的悬空指针。如果是循环链表本身已经成环问题反而更简单。循环链表没有头尾之分所谓旋转就是换个起点。你只需要找到新的起始节点把它作为头节点即可不需要做任何指针重连操作。这个变体虽然简单但能帮你加深对链表结构取决于视角这个概念的理解。6.5 一句题外话题号记不记其实无所谓在Leetcode上旋转链表这个问题的题号在不同版本、不同国家的网站上会有差异有人记成61有人记成107还有人只是随手记在自己的刷题本上。真正重要的是你理解了这个旋转的操作本质。我在面试中从来不会说我刷过第61题而是直接讲思路。面试官关心的永远是解题思路本身而不是你背下的题号数字。所以如果你在某个地方看到Leetcode 107 旋转链表这个标题不用纠结它到底是第几题顺着链表旋转的逻辑去理解就好。这也是为什么我在写这篇博客时没有把题号当回事题号只是索引算法才是核心。最后再分享一个小体会这道题我前前后后刷了大概五遍每一遍都有新的收获。第一遍学模板第二遍搞懂为什么成环第三遍开始能给别人讲清楚第四遍能在面试时直接写对第五遍是为了确认——在最紧张的情况下我还能不能靠肌肉记忆写出来。链表题的境界大概就是这样一层一层练出来的。希望这篇足够细致的拆解能帮你少走一点我当时走过的弯路。
