LeetCode 61 旋转链表题解：成环法与双指针法详解

很多刷 LeetCode 的朋友看到“旋转链表”这道题，第一反应多半是：这不就是把后面几个节点挪到前面来吗？听起来很简单，可真上手一写，指针绕两下就开始晕，甚至写完提交还会弹出“链表中有环”这种让人摸不着头脑的报错。这篇文章，我准备把LeetCode 61. 旋转链表的来龙去脉拆开讲清楚，覆盖两种主流写法的核心思路、边界条件，以及我在刷题和面试里实际踩过的坑。如果你正卡在这道题上，或者想把它讲给面试官听，这篇题解应该能帮上忙。

1. 读懂旋转链表的本质：不是平移，而是切链与重连

1.1 题目描述与两个关键示例

先回顾一下题目本身。给定一个链表，将链表的每个节点向右移动k个位置。注意这里说的是“每个节点”，而不是“第几个节点”。这个表述意味着旋转操作是对整条链的姿态调整，而不是简单地移动一个局部块。

举官方的例子：1 -> 2 -> 3 -> 4 -> 5，k = 2，结果是4 -> 5 -> 1 -> 2 -> 3。再看0 -> 1 -> 2，k = 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 -> 5，n = 5，k = 2。新尾是第5 - 2 = 3个节点，也就是节点3；新头是第4个节点，也就是节点4。旋转结果是4 -> 5 -> 1 -> 2 -> 3，完全吻合。

为什么是这个公式？换个角度想：旋转后，原链表的后k个节点被整体挪到了前面。所以“新头”就是从倒数第k个节点开始的那个节点。链表里找倒数第k个节点，正着数就是第n - k + 1个。中间那段（从第 1 个到第n - k个）则被移到了尾部。

这两个位置公式，是下面所有代码的基石。建议你先亲手把几个例子画出来，确认这个公式是对的，再去写代码。

3. 解法一：尾首成环后按位剪断，代码短且不易越界

3.1 成环法的三个步骤

成环法的核心思想，是先把链表“首尾相连”变成一个环，然后在合适的位置把环重新剪开。这样做的好处是，从头到尾只有一次“成环”和一次“断环”，指针来回跳动的次数少，代码鲁棒性高。

三个步骤如下：

1. 遍历链表，记录长度n，同时让尾节点的next指向头节点，形成环。
2. 计算k = k % n，如果k == 0，先把环断开再返回原头节点。
3. 找到新尾节点（第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 head，OJ 检测时会在链表里无限循环，直接报错。

所以，k % n == 0时的处理，与其说是一个“优化分支”，不如说是一个“安全分支”。它保证了函数在任何情况下返回的链表都绝对没有环。

3.4 成环法的最坏情况与复杂度

成环法的时间复杂度是 O(n)，空间复杂度是 O(1)。第一遍遍历做了n - 1次next跳转，第二遍找新尾最多走n - 2次，总步数在2n量级内。不管k多大，取模之后都只受n影响，这一点非常稳定。

成环法在面试里的优势是：代码短，思路直观，一旦理解了“先成环再剪断”的模式，几乎不会写出指针错乱的 bug。如果你是第一次做这道题，我个人更推荐先掌握这个解法。

4. 解法二：快慢双指针一趟定位，适合讲思路的过程

4.1 双指针法的两个阶段

第二种解法不把链表成环，而是直接用快慢指针定位切割点。它的核心思想是：利用快指针先走k步，制造一个“快慢指针之间相差k个节点”的距离。然后两个指针一起走，当快指针到达尾节点时，慢指针恰好站在新尾节点的位置。

这个方法分成两个阶段：

1. 快指针先走k步，也就是从head出发走k条边，到达第k + 1个节点。
2. 快慢指针同时走，直到快指针到达尾节点（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 个节点”那类题的思路一脉相承，对后面刷别的题有帮助。

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的倍数时，比如链表长度 5，k = 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, limit=10): cur = head for _ in range(limit): if not cur: print("None") return print(cur.val, end=" -> ") cur = cur.next print("...")

limit参数是关键，它可以防止链表成环时打印函数死循环。你用limit=10去打印一个长度只有 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 从一开始就能避免。