如何旋转链表？为什么常先把链表连成环再断开？

简化版

旋转链表可以先统计长度 n，把尾节点连到头节点形成环，再在新尾节点处断开。右旋 k 位等价于新尾在第 n - k % n - 1 个节点，新头是它的下一个节点。

详细版

右旋链表的意思是把末尾 k 个节点搬到前面。例如 1 -> 2 -> 3 -> 4 -> 5 右旋 2 位后是 4 -> 5 -> 1 -> 2 -> 3。

常见步骤：

遍历一次得到长度 n 和尾节点 tail。
令 k = k % n，如果 k == 0 直接返回原头。
把 tail.next = head，形成一个环。
新尾位置是从原头开始走 n - k - 1 步。
newHead = newTail.next，再令 newTail.next = null 断环。

整个过程时间复杂度 O(n)，空间复杂度 O(1)。重点是理解“旋转不是移动节点值，而是改变断点”。

完整版教学

一、旋转链表的本质是改变头尾断点

链表右旋不是把每个节点真的一个个搬运，而是改变哪一个节点当头、哪一个节点当尾。原链表 1 -> 2 -> 3 -> 4 -> 5 右旋 2 位后，节点顺序沿着某条路径仍然是 4 -> 5 -> 1 -> 2 -> 3。

如果把原尾 5 接回原头 1，你会得到：

1 -> 2 -> 3 -> 4 -> 5
^                   |
|___________________|

在这个环上，任何节点都可以成为头。右旋的工作就变成“找到正确的新尾，然后断开它的 next”。这个视角能把复杂的搬移过程降成一次接环加一次断环。

二、为什么必须先对 k 取模

旋转次数可能远大于链表长度。长度为 5 的链表右旋 7 次，效果和右旋 2 次完全一样，因为每 5 次回到原状。

公式是：

effectiveK = k % n

比如 n = 5, k = 12，有效旋转次数是 2。如果不取模，按 k 次逐个移动尾节点到头部会退化成 O(k*n) 或 O(k)，当 k = 10^9 时不可接受。取模不是小优化，而是把问题重新归约到一个周期内。

三、新尾节点位置怎么推出来

右旋 k 位后，原链表的后 k 个节点会到前面，前 n-k 个节点会到后面。因此新头是原链表第 n-k 个节点，新尾是它前面的那个节点。

用 0 基下标看更直观：

原链表：0:1  1:2  2:3  3:4  4:5
n = 5, k = 2
新头下标 = n - k = 3 -> 节点 4
新尾下标 = n - k - 1 = 2 -> 节点 3

所以从 head 出发走 n-k-1 步，到达新尾。然后 newHead = newTail.next，最后 newTail.next = null。如果这里少走一步或多走一步，结果会整体错位，这是旋转链表最常见的边界坑。

四、为什么接环再断比逐个移动更稳定

逐次旋转的想法是每次找到尾节点，把尾节点摘下来放到头部。单次操作需要找到尾节点的前驱，通常要 O(n)，做 k 次就是 O(k*n)。

接环法只遍历两次左右：

方法	核心操作	时间复杂度	稳定性
逐次搬尾	每次找尾前驱	O(k*n)	容易超时
快慢指针找断点	找倒数第 k 个位置	O(n)	需要处理 k 取模
接环再断	尾接头，找新尾断开	O(n)	语义最直观

接环法的优势是“旋转”这个动作和“选断点”天然对应。你不用真的移动节点，只是把链表看成一圈，然后选择从哪里剪开。

五、边界情况如何处理

边界通常比主体逻辑更容易出错。空链表、单节点链表、k = 0、k 是长度整数倍，都应该直接返回原头。

可以按这个顺序防守：

if (!head || !head.next || k === 0) return head;
// 统计 n 和 tail
k = k % n;
if (k === 0) return head;
// 接环、找新尾、断环

注意第二个 k === 0 必须在知道长度后判断，因为 10 % 5 = 0。如果省略这个判断，代码仍可能返回正确结果，但会无意义地接环断环，增加出错机会。

六、复杂度和工程语义

旋转链表的时间复杂度是 O(n)，因为统计长度要遍历一次，找新尾最多再走 n 步以内。空间复杂度是 O(1)，没有新建随节点数量增长的结构。

工程上要注意，链表旋转会改变原节点之间的连接关系。如果还有别的对象保存了某个中间节点引用，它看到的后继关系会改变。这和数组切片返回新数组不一样，链表操作通常是原地修改。

记忆钩子：右旋链表先把“直线”接成“圆”，再在第 n-k-1 个节点后剪开；旋转的本质是换断点。

七、常见误区与追问

误区：右旋 k 位就是循环移动 k 次。 这样在大 k 下会很慢，正确做法是先 k % n。
误区：新尾是第 n-k 个节点。 第 n-k 个节点是新头，新尾是它前一个，也就是下标 n-k-1。
误区：接成环后忘记断开。 忘记 newTail.next = null 会得到环形链表，遍历时可能死循环。
追问：左旋怎么做？ 左旋 k 位等价于右旋 n - k % n 位，或者直接让新尾在第 k-1 个节点。
追问：能用快慢指针吗？ 可以，先让快指针走 k % n 步，再一起走到快指针到尾，慢指针附近就是断点，但仍要先知道长度或处理 k 超长。

八、加强记忆

这题不要把“旋转”想成搬运，想成“环上剪一刀”。先统计长度确定周期，再尾接头形成环，最后按 n-k-1 找新尾并断开。只要这三个动作顺序不乱，空链表、单节点、k 超大、k 为长度倍数这些边界都能自然收住。

简化版

详细版