很多刷 LeetCode 的朋友看到“旋转链表”这道题第一反应多半是这不就是把后面几个节点挪到前面来吗听起来很简单可真上手一写指针绕两下就开始晕甚至写完提交还会弹出“链表中有环”这种让人摸不着头脑的报错。这篇文章我准备把LeetCode 61. 旋转链表的来龙去脉拆开讲清楚覆盖两种主流写法的核心思路、边界条件以及我在刷题和面试里实际踩过的坑。如果你正卡在这道题上或者想把它讲给面试官听这篇题解应该能帮上忙。1. 读懂旋转链表的本质不是平移而是切链与重连1.1 题目描述与两个关键示例先回顾一下题目本身。给定一个链表将链表的每个节点向右移动k个位置。注意这里说的是“每个节点”而不是“第几个节点”。这个表述意味着旋转操作是对整条链的姿态调整而不是简单地移动一个局部块。举官方的例子1 - 2 - 3 - 4 - 5k 2结果是4 - 5 - 1 - 2 - 3。再看0 - 1 - 2k 4结果是2 - 0 - 1。第二个例子很有意思——链表长度只有 3但k却给了 4说明题目默认k可以大于链表长度。这一点直接影响解题策略后面我会专门展开。从结构上看旋转一次链表本质上就是做两件事把原来的尾节点接到头节点上再在合适的位置把链剪断。你说它是“平移”也好“翻转”也好最终落到代码层面都是改指针的指向。理解到这一层题目就已经解了一半。1.2 链表旋转相比数组旋转难在哪如果这道题改成“旋转数组”比如[1,2,3,4,5]右移 2 位很多人的第一直觉仍然是“把数组拆两段再拼起来”。数组因为下标随机访问你可以轻松算出每个元素的新位置但链表不行你只能沿着next指针一条路走到黑。这就引出了链表的第一个特点你无法像数组那样用 O(1) 时间跳到任意位置所有定位操作都必须依赖遍历。第二个特点是链表节点是分散在内存里的旋转操作必须同时维护多个指针的引用否则很容易丢链。比如你把尾节点的next指向了头节点如果不先记录头节点位置整条链就凭空消失了。所以这道题真正考察的不是“你会不会做旋转”而是“你能不能安全地在链上进行切断和重接”。明白了这一点再去看各种解法思路就会清晰很多。2. 动手前先搞定数学长度、取模与切割点推导2.1 第一次遍历链长是一切操作的“尺子”不管是哪种解法第一步几乎都是先遍历链表求出长度n。这一步逃不掉因为只有知道了总长度才能判断k的实际有效性也才能算出“新头节点”和“新尾节点”的位置。求长度本身很简单def get_length(head): n 0 cur head while cur: n 1 cur cur.next return n但这里有一个非常容易忽略的点在第一种解法成环法里我们不是为了求长度而求长度而是要在遍历的过程中顺便找到原链表的尾节点。因为在成环法里尾节点的next需要指向原来的头节点形成环。这一个“顺便”能让代码少遍历一遍后面我会在代码里展示。2.2 取模不是优化而是正确性的一部分很多初学者看到k很大会想我把它对n取模不就行了吗乍一看这确实是个优化手段。但更重要的是如果不取模程序逻辑本身就是错的。为什么因为旋转n次之后链表会回到原样。比如1 - 2 - 3旋转 3 次得到的就是1 - 2 - 3本身。所以旋转k次和旋转k % n次结果完全一致。当k比n大很多时实际的旋转次数被大大压缩代码的执行效率也跟了上来。取模还有一个隐藏好处就是后面计算“新头节点位置”的时候k一定在0 k n的范围内。这让各种下标推导变得安全不会出现负数或越界访问。2.3 旋转后新头和新尾的位置公式这是全题最关键的推导。假设链表长度为n节点编号从头到尾依次是1, 2, ..., n。向右旋转k次这里的k已经取模旋转后新尾节点是原链表的第n - k个节点当k 0时新头节点是新尾节点的下一个节点也就是原链表的第n - k 1个节点用例子验证一下1 - 2 - 3 - 4 - 5n 5k 2。新尾是第5 - 2 3个节点也就是节点3新头是第4个节点也就是节点4。旋转结果是4 - 5 - 1 - 2 - 3完全吻合。为什么是这个公式换个角度想旋转后原链表的后k个节点被整体挪到了前面。所以“新头”就是从倒数第k个节点开始的那个节点。链表里找倒数第k个节点正着数就是第n - k 1个。中间那段从第 1 个到第n - k个则被移到了尾部。这两个位置公式是下面所有代码的基石。建议你先亲手把几个例子画出来确认这个公式是对的再去写代码。3. 解法一尾首成环后按位剪断代码短且不易越界3.1 成环法的三个步骤成环法的核心思想是先把链表“首尾相连”变成一个环然后在合适的位置把环重新剪开。这样做的好处是从头到尾只有一次“成环”和一次“断环”指针来回跳动的次数少代码鲁棒性高。三个步骤如下遍历链表记录长度n同时让尾节点的next指向头节点形成环。计算k k % n如果k 0先把环断开再返回原头节点。找到新尾节点第n - k个节点把它的next置为None下一个节点自然就是新头节点。3.2 Python 实现与逐行注释def rotateRight(head, k): # 边界条件空链表、单节点链表、k为0 都直接返回 if not head or not head.next or k 0: return head # 第一步求长度同时找到尾节点 n 1 tail head while tail.next: tail tail.next n 1 # 现在 tail 是原链表的尾节点 # 记录原头准备成环 tail.next head # 第二步取模处理 k 大于等于 n 的情况 k % n if k 0: # 如果取模后是0说明旋转后还是原链表先把环断开 tail.next None return head # 第三步找新尾节点需要从 head 走 (n - k - 1) 步 new_tail head for _ in range(n - k - 1): new_tail new_tail.next # 此时 new_tail.next 就是新头 new_head new_tail.next # 剪断环恢复链表结构 new_tail.next None return new_head这里唯一需要留神的循环步数是n - k - 1。很多人会写成n - k或者n - k - 2差一步结果就完全不对。为什么是n - k - 1因为你要到达的是第n - k个节点而从第 1 个节点出发到达第m个节点需要走m - 1步。所以到达第n - k个节点需要走n - k - 1步。3.3 为什么 k % n 0 时要单独处理如果你跳过这个判断直接去循环找新尾会发生什么当k 0时新尾应该是第n个节点也就是原来的尾节点。循环会走n - 0 - 1 n - 1步正好停在尾节点。然后把尾节点的next置为None似乎也能得到原链表问题在于此时链表的环还带着呢。虽然你把尾节点的next断开了但是如果只走这一遍成环那一步已经把尾节点指向了头节点你是用“剪断”的方式恢复了原样。逻辑上没问题但多了一步不必要的循环。更重要的是如果不小心在成环后直接return headOJ 检测时会在链表里无限循环直接报错。所以k % n 0时的处理与其说是一个“优化分支”不如说是一个“安全分支”。它保证了函数在任何情况下返回的链表都绝对没有环。3.4 成环法的最坏情况与复杂度成环法的时间复杂度是 O(n)空间复杂度是 O(1)。第一遍遍历做了n - 1次next跳转第二遍找新尾最多走n - 2次总步数在2n量级内。不管k多大取模之后都只受n影响这一点非常稳定。成环法在面试里的优势是代码短思路直观一旦理解了“先成环再剪断”的模式几乎不会写出指针错乱的 bug。如果你是第一次做这道题我个人更推荐先掌握这个解法。4. 解法二快慢双指针一趟定位适合讲思路的过程4.1 双指针法的两个阶段第二种解法不把链表成环而是直接用快慢指针定位切割点。它的核心思想是利用快指针先走k步制造一个“快慢指针之间相差k个节点”的距离。然后两个指针一起走当快指针到达尾节点时慢指针恰好站在新尾节点的位置。这个方法分成两个阶段快指针先走k步也就是从head出发走k条边到达第k 1个节点。快慢指针同时走直到快指针到达尾节点fast.next为None。此时慢指针已经来到了第n - k个节点也就是新尾节点。4.2 Python 实现与逐行注释def rotateRight(head, k): # 边界条件 if not head or not head.next or k 0: return head # 第一趟求链长并保留尾节点 n 1 tail head while tail.next: tail tail.next n 1 k % n if k 0: return head # 快指针先走k步 fast head slow head for _ in range(k): fast fast.next # 快慢一起走fast到达最后一个节点时停止 while fast.next: fast fast.next slow slow.next # 此时 slow 是旋转后的新尾slow.next 是旋转后的新头 new_head slow.next slow.next None fast.next head return new_head注意这里和成环法有一个明显区别双指针法在算完k % n后如果k 0直接return head就行。因为它并没有形成环返回的就是一条正常的链表。4.3 证明慢指针落点的正确性这个方法里最容易被问倒的一个问题是为什么fast到达尾节点时slow正好是第n - k个节点推导过程如下。fast先走了k步到达第k 1个节点。然后fast从第k 1个节点移动到尾节点第n个节点还需要走n - (k 1)条边。在同一段时间里slow也从第 1 个节点走了n - (k 1)条边于是它到达的节点编号是1 (n - k - 1) n - k正好是第n - k个节点也就是新尾节点。这个推导很干净建议你在面试时能写出来比用手比划半天更有说服力。4.4 双指针法和成环法的对比选型对比维度成环法双指针法核心思路先成环后剪断快慢指针拉开距离定位切割点代码长度稍短稍长但逻辑清晰k % n 0处理需要先断环再返回直接返回即可调试友好度如果忘了断环问题隐蔽没有成环动作不容易出现环问题面试讲解难度中等较高推导过程很直观如果是在白板上写代码我倾向用成环法因为它的代码更紧凑手写出错概率低。如果是在力扣上做这道题两种都可以。双指针法的思想更通用它和“查找链表倒数第 k 个节点”那类题的思路一脉相承对后面刷别的题有帮助。5. 高频边界条件与常见翻车点自查清单5.1 空链表、单节点链表先防御再动手链表的边界问题核心就是“能不能访问.next”。如果链表为空你调用head.next会抛空指针如果链表只有一个节点第二遍遍历都无法进行。所以几乎所有链表题的标准开头我都会写这样一行防御if not head or not head.next or k 0: return head这行代码同时处理了三种情况空链表、单节点链表、以及k等于 0 的情况。有人会把k 0的判断写晚一点也不是不行但写在这里最省事后续逻辑就不用再为这些分支操心了。5.2 k 的三种边界0、倍数、超大值k 0很好理解旋转 0 次等于没转。k是链长n的倍数时比如链表长度 5k 5或k 10旋转之后同样等于没转。这两种情况在取模之后都是k % n 0所以代码里能统一处理。真正考验人的是k非常大比如k 1000000000。如果不取模你让fast先走k步它可能已经走了几十万次甚至更多性能直接拉胯。取模之后这个数字会立刻缩小到0 ~ n-1代码跑得飞快。5.3 断链顺序先置空还是先重连这是新手最容易踩的坑。举个例子在双指针法里我们有这样两行操作new_head slow.next slow.next None fast.next head如果我先执行fast.next head这时链表变成什么样原来fast还指向尾节点你把它的next指向head链表就形成了一个环。紧接着你再去访问slow.next它还是新头节点看着没问题但整条链已经在一个环里转了。之后再怎么slow.next None都救不回来因为环已经存在遍历会死循环。正确的顺序是先拿到新头节点的引用再断开slow.next最后让原来尾节点的next指向原头节点。核心原则就一句话先记录再改指针。5.4 看不见的环OJ 超时的一个隐蔽原因如果你在成环法里忘了处理k % n 0或者忘记在某处把尾节点的next置空力扣通常不会提示“格式错误”而是给你一个“超出时间限制”。因为链表变成环之后很多内部校验函数会在遍历链表时陷入死循环。这种 bug 的特点就是本机测试小数据可能看不出问题因为你的打印函数也许只访问了前几个节点就结束了。一旦提交OJ 会尝试遍历整条链问题就暴露了。我在本地调试时会特别加一个打印函数打印前n 2个节点如果打印数量超过了链表长度基本就可以断定有环存在。这是一种非常直观的检测方式。5.5 本地验证写一个打印函数快速检查配合这道题我建议你写一个简单的辅助函数用来验证旋转结果def print_list(head, limit10): cur head for _ in range(limit): if not cur: print(None) return print(cur.val, end - ) cur cur.next print(...)limit参数是关键它可以防止链表成环时打印函数死循环。你用limit10去打印一个长度只有 5 的链表如果第五个节点之后还在输出那就说明链表里很可能有环。这个习惯在调试任何链表题时都非常实用。6. 旋转链表背后的通用思维环形位移的几种变形与延伸6.1 从链表到数组同一道题的三种解法家族“旋转/轮转”这类操作其实在算法题里是一个家族。数组版本的题目是LeetCode 189. 轮转数组它有两种经典解法一种是用额外数组另一种是“三次反转”。三次反转的思路是先把整个数组反转再分别反转前k个元素和后n-k个元素用 O(1) 额外空间完成原地旋转。但三次反转的思路在链表上行不太通。因为数组反转是基于下标交换的而链表如果要原地反转某一段你得先定位到那一段的头尾再逐个节点反转next指针复杂度非常高代码也容易出错。链表题里更顺手的做法就是本文前面讲的“成环法”或“双指针法”。从这个对比可以看出很多常数级的优化技巧和语言特性强相关不必强求套用到所有数据结构上。链表就用链表自己的玩法。6.2 快慢指针在其他链表题中的复用双指针法的思想非常值得你收藏。它本质上是“先拉开固定距离再同步移动”的套路可以用在很多地方LeetCode 19. 删除链表的倒数第 N 个节点快指针先走N步然后快慢同步走快指针到结尾时慢指针正好在倒数第N个节点。LeetCode 876. 链表的中间结点快指针走两步、慢指针走一步快指针到结尾时慢指针在中点。LeetCode 141. 环形链表同样用快慢指针如果有环两者最终会相遇。说到底快慢指针不是一个“技巧”而是一种“利用速度差来测量链表结构”的思维方式。你在这道题里把它理解了后面同类题目基本都能轻松迁移。6.3 我的练习建议如果你是第一次接触这道题我的建议很简单先别急着看代码拿一张纸把“1 - 2 - 3 - 4 - 5 - None”画出来然后把k 2的旋转过程手动模拟一遍标出每一步的指针变化。然后用成环法写一遍代码再用双指针法写一遍。两个解法都跑通之后再去看k 0、k n、k n 1这些边界值把每一种情况都验证一遍。等你把这道题彻底吃透再去刷刚才提到的快慢指针相关题目你会发现很多链表题的思路都是互通的。我个人在带人刷题的时候经常会用 61 题作为“链表指针操作”这一阶段的收尾题——因为它既不涉及复杂的递归也不涉及高阶数据结构却能把你对链表的“断链”“接链”“防环”基本功全部考验一遍。最后分享一个我实际写题时的小习惯每次改完链表的next指针我都会在心里默念一句“这个节点的原引用还在不在它的新引用指向哪里”。链表的操作本质上就是引用的转移只要每一步都知道“谁在引用我、我引用了谁”很多奇奇怪怪的 bug 从一开始就能避免。