61. 旋转链表

61. 旋转链表

题目描述

给你一个链表的头节点 head，把链表每个节点向右移动 k 个位置，返回旋转后的链表。

示例 1

text
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2

text
输入：head = [0,1,2], k = 4
输出：[2,0,1]

约束

  • 链表中节点数目范围是 [0, 500]
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 10^9

核心思路

这题的关键不是“真的转 k 次”，而是先搞清楚：

  1. 链表长度如果是 n，那么右移 k 次，等价于右移 k % n 次。
  2. 右移之后：
    • 新的头节点，其实是原链表里第 n - (k % n) 个节点。
    • 新的尾节点，就是它前面的那个节点。
  3. 所以本题本质上是在做：
    • 先找到链表长度 n
    • 再找到新的头和新的尾
    • 最后断开并重新连接

这题至少有两种常见做法：

  • 解法一：数组模拟 / 记录所有节点
  • 解法二：链表成环后断开（最优做法）

解法一：数组记录所有节点

思路拆解

如果我们把链表所有节点按顺序放进数组：

text
[1, 2, 3, 4, 5]

当 k = 2 时，相当于把最后两个节点挪到最前面：

text
[4, 5, 1, 2, 3]

对应到原链表里：

  • 长度 n = 5
  • 真正需要移动的次数 step = k % n = 2
  • 新头节点下标 = n - step = 3（0 下标）
  • 新尾节点下标 = n - step - 1 = 2

所以：

  • nodes[3] 是新头
  • nodes[2] 是新尾
  • 原尾巴要指向原头
  • 新尾巴要断开

一步一步写出算法

第一步：处理特殊情况

如果链表为空、只有一个节点，或者 k = 0，那就不用转。

ts
if (head === null || head.next === null || k === 0) {
    return head
}

第二步：遍历链表，把节点放进数组

我们需要：

  • 得到链表长度 n
  • 后面通过下标快速找到“新头”和“新尾”
ts
const nodes: ListNode[] = []
let cur = head
while (cur !== null) {
    nodes.push(cur)
    cur = cur.next
}

第三步：计算真正需要旋转多少次

因为转 n 次会回到原状，所以：

ts
const n = nodes.length
const step = k % n

如果 step == 0，说明转完还是原链表。

ts
if (step === 0) {
    return head
}

第四步：定位新头和新尾

ts
const newHead = nodes[n - step]
const newTail = nodes[n - step - 1]
const oldTail = nodes[n - 1]

第五步：重新连接

原尾接回原头，形成新的顺序；再把新尾断开。

ts
oldTail.next = head
newTail.next = null
return newHead

代码实现（TypeScript）

ts
class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0
        this.next = next ?? null
    }
}

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (head === null || head.next === null || k === 0) {
        return head
    }

    const nodes: ListNode[] = []
    let cur: ListNode | null = head
    while (cur !== null) {
        nodes.push(cur)
        cur = cur.next
    }

    const n = nodes.length
    const step = k % n
    if (step === 0) {
        return head
    }

    const newHead = nodes[n - step]
    const newTail = nodes[n - step - 1]
    const oldTail = nodes[n - 1]

    oldTail.next = head
    newTail.next = null

    return newHead
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

这一解法的优缺点

优点：

  • 思路直观
  • 很容易想清楚“新头”和“新尾”是谁
  • 适合第一次做这题

缺点：

  • 额外用了数组存节点
  • 不是空间最优

解法二：链表成环后断开（推荐）

这是这题最经典、也最优雅的做法。

思路拆解

还是以：

text
1 -> 2 -> 3 -> 4 -> 5, k = 2

为例。

如果我们先找到尾节点，然后把它指向头节点：

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

链表就成了一个环。

此时右移 2 位之后，新的链表应该是：

text
4 -> 5 -> 1 -> 2 -> 3

也就是说：

  • 新头是第 n - step 个节点
  • 新尾是它前一个节点
  • 把新尾的 next 断开，就得到答案

为什么是 n - step？

假设链表长度是 n，右移 step 位：

  • 最后 step 个节点会跑到前面
  • 所以新的头节点，正好是原链表中第 n - step 个位置（从 0 下标看是第 n - step 个节点）

例如：

text
n = 5, step = 2
新头下标 = 5 - 2 = 3
也就是值为 4 的节点

一步一步写出算法

第一步：处理边界情况

ts
if (head === null || head.next === null || k === 0) {
    return head
}

第二步：先统计链表长度，并找到尾节点

这一步的目的有两个：

  • 计算 k % n
  • 之后把尾节点接回头节点，形成环
ts
let n = 1
let tail = head
while (tail.next !== null) {
    tail = tail.next
    n += 1
}

第三步：计算真正旋转步数

ts
const step = k % n

如果 step == 0，说明不需要动。

ts
if (step === 0) {
    return head
}

第四步：先把链表连成环

ts
tail.next = head

第五步：找到新的尾节点

新的尾节点应该是原链表的第 n - step - 1 个节点。

所以从 head 出发走 n - step - 1 步：

ts
let newTail = head
for (let i = 0; i < n - step - 1; i++) {
    newTail = newTail.next!
}

第六步：拿到新的头节点，并断开环

ts
const newHead = newTail.next
newTail.next = null
return newHead

代码实现（TypeScript）

ts
class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0
        this.next = next ?? null
    }
}

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (head === null || head.next === null || k === 0) {
        return head
    }

    let n = 1
    let tail = head
    while (tail.next !== null) {
        tail = tail.next
        n += 1
    }

    const step = k % n
    if (step === 0) {
        return head
    }

    tail.next = head

    let newTail = head
    for (let i = 0; i < n - step - 1; i++) {
        newTail = newTail.next!
    }

    const newHead = newTail.next
    newTail.next = null
    return newHead
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

这一解法的优缺点

优点：

  • 只遍历常数次链表
  • 不需要额外数组
  • 是这题最推荐的标准解法

缺点：

  • “先成环再断开”的思路，第一次看时不如数组法直观

两种解法对比

解法时间复杂度空间复杂度特点
数组记录节点O(n)O(n)容易理解，适合入门
成环后断开O(n)O(1)最经典，面试更推荐

如果你是第一次做这题，建议先完全理解数组法；如果你想把这题真正做熟，最后一定要掌握成环断开法。

面试时最容易忽略的点

1. k 可能非常大

不要真的旋转 k 次，而是：

ts
k %= n

2. 空链表要先判断

如果 head = null，直接去算长度会报错。

3. k % n == 0 时不要乱断链

这种情况下，旋转后和原链表完全一样，直接返回原头节点即可。

4. 新尾节点的位置别写错

  • 新头：第 n - step 个节点
  • 新尾：第 n - step - 1 个节点

这是本题最关键的位置关系。

我们手动模拟一遍最优解

以：

text
head = [1,2,3,4,5], k = 2

为例。

第 1 步：统计长度

text
n = 5

第 2 步：计算真正移动次数

text
step = 2 % 5 = 2

第 3 步：尾节点连回头节点

text
1 -> 2 -> 3 -> 4 -> 5 -> 1 -> ...

第 4 步：找新的尾节点

新的尾节点位置：

text
n - step - 1 = 5 - 2 - 1 = 2

也就是值为 3 的节点。

第 5 步：确定新头节点

text
new_head = 3.next = 4

第 6 步：断开

把 3.next = null，得到：

text
4 -> 5 -> 1 -> 2 -> 3

一句话总结

这题的本质是：先用 k % n 消掉无效旋转，再准确找到“新头”和“新尾”。

  • 想得直观：用数组
  • 想做到最优：把链表连成环，再在正确位置断开

推荐你最后记住的标准写法

如果你准备面试，建议优先记下面这个版本：

ts
class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0
        this.next = next ?? null
    }
}

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (head === null || head.next === null || k === 0) {
        return head
    }

    let n = 1
    let tail = head
    while (tail.next !== null) {
        tail = tail.next
        n += 1
    }

    k %= n
    if (k === 0) {
        return head
    }

    tail.next = head

    let newTail = head
    for (let i = 0; i < n - k - 1; i++) {
        newTail = newTail.next!
    }

    const newHead = newTail.next
    newTail.next = null
    return newHead
}