LeetCode 61. 旋转链表

约 5 分钟
文章信息 19 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 历史考题 50-100 面试经典 150 题 腾讯 字节 阿里 华为 微软 美团 百度 快手 滴滴 虾皮 猿辅导
标签
双指针 链表

题目描述

✅ 61. 旋转链表

image-20260928194337849

image-20260928194337850

题意分析

将单链表向右旋转 k 个位置，返回旋转后的头节点。向右旋转一次，就是把原来的尾节点移到头部，其余节点依次后移。

旋转只改变链表的起点与终点，节点值不变，原有节点的环形先后顺序也不变。k 可以远大于节点数量，不应真的重复执行 k 次搬移；空链表、单节点链表和零次旋转都应保持原样。

解法：成环后定位新尾节点

核心思路

[!blue]

设链表长度为 length。连续右移 length 次后，每个节点都会回到原位置，因此只需处理 move = k % length 次有效旋转。先遍历一次得到长度和原尾节点，若 move == 0，直接返回原头即可。

当 move > 0 时，旋转等价于把最后 move 个节点整体接到前面，同时保持前后两段各自的顺序。原前段有 length - move 个节点，所以它的最后一个节点会成为新尾；后一个节点就是新头。

为了接好两段，可以先令原尾指向原头，把链表连成环。原来后段的末尾就已经接上前段的开头，只需在前段末尾断开一次，就得到所需顺序。

按从 1 开始的节点序号，新尾是第 length - move 个节点；从原头出发只需走 length - move - 1 条连接。必须先保存 newHead = newTail.next，再将 newTail.next 置空，否则断链后就失去了新头的入口。最后返回保存的新头，原有节点全部保留且链表不再成环。

解题步骤

  1. 若链表为空、只有一个节点，或 k == 0，直接返回原头。
  2. 遍历链表，得到 length 和原尾 tail。
  3. 计算 move = k % length；有效旋转次数为零时返回原头。
  4. 将 tail.next 指向原头，从原头走 length - move - 1 步定位新尾。
  5. 保存新尾的后继为新头，再断开新尾的后继指针，返回新头。

代码实现

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }

        int length = 1;
        ListNode tail = head;

        while (tail.next != null) {
            tail = tail.next;
            length++;
        }

        int move = k % length;

        if (move == 0) {
            return head;
        }

        // 先成环，再在新的尾节点处断开。
        tail.next = head;
        // 新尾是第 length 减 move 个节点，从头需要少一步连接。
        int stepsToNewTail = length - move - 1;
        ListNode newTail = head;

        for (int i = 0; i < stepsToNewTail; i++) {
            newTail = newTail.next;
        }

        // 先保存新入口，再断开环。
        ListNode newHead = newTail.next;

        newTail.next = null;

        return newHead;
    }
}

func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil || k == 0 {
        return head
    }

    length := 1
    tail := head
    for tail.Next != nil {
        tail = tail.Next
        length++
    }

    move := k % length
    if move == 0 {
        return head
    }

    // 环形连接后，找到新的尾节点再断开。
    tail.Next = head
    // 新尾是第 length 减 move 个节点，从头需要少一步连接。
    stepsToNewTail := length - move - 1
    newTail := head
    for i := 0; i < stepsToNewTail; i++ {
        newTail = newTail.Next
    }
    // 先保存新入口，再断开环。
    newHead := newTail.Next
    newTail.Next = nil
    return newHead
}

复杂度分析

设链表长度为 $n$。

  • 时间复杂度：$O(n)$。统计长度遍历一次，定位新尾最多再走 $n-1$ 步，与原始 k 的大小无关。
  • 空间复杂度：$O(1)$，只使用常数个指针和整数变量，直接调整现有节点的连接。

关键点总结

[!green]

  • 先取模去掉完整转圈，再将最后 move 个节点作为整体移到前面。
  • 新尾由前段长度确定：节点序号是 length - move，移动步数还要减一。
  • 原尾接原头完成两段连接，新尾断开完成旋转。

易错点总结

[!yellow]

  • 空链表必须在统计长度和取模前处理，避免空指针或除以零。
  • 混淆节点序号与移动步数会多走一步；起点已经是第一个节点，不能再走 length - move 步。
  • move == 0 时应在成环前返回，不能留下已经连成环却未断开的链表。
  • 先断开新尾再读取它的后继，会丢失新头；顺序必须是先保存、后断开。
  • 成环后忘记把新尾的后继置空，返回的会是环形链表而不是有限链表。

相似题目

题目 难度 关联与区别
189. 轮转数组 中等 同样先对长度取模确定真正旋转量，数组通过反转或循环搬移，本题通过接环再断开。
19. 删除链表的倒数第 N 个结点 中等 定位新的断点可视为找到倒数k个位置之前的节点，需明确前驱与目标的区别。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/42871102
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！