LeetCode 61. 旋转链表

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

题目描述

✅ 61. 旋转链表

image-20230312223031835

image-20230312223036587

题意分析

给定链表头节点和整数 k，要求把链表整体向右旋转 k 个位置，也就是每个节点都向后挪 k 格，超出末尾的部分绕回到开头，最后返回新的头节点。

约束里有一个强烈的信号：k 的范围可以达到 $2 \times 10^9$，远大于链表长度上限 500。这说明 k 本身不能直接当步数用，题目在暗示「旋转是周期性的」——设链表长度为 n，旋转 n 次会回到原样，所以真正有效的旋转量只取决于 k 对 n 的余数。特别地，当 k % n == 0 时链表等于完全不动，应当原样返回。

边界情况也要先想清楚：空链表、单节点链表旋转多少次都是自己；k == 0 时无事发生。这三种情况都可以在最开始直接返回。

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

核心思路

问题关键：逐次把尾节点搬到头部需要 $O(kn)$；而链表每旋转 n 次就恢复原状，所以有效位移只有 move = k % n。

为什么先成环：右移 move 位，本质是把最后 move 个节点接到最前面。先让原尾连接原头，所有节点就在同一个环中，只需找到新尾并断开一次，比手动拆接两段更不容易丢链。

位置不变量：新尾是原链表第 n - move 个节点，即从原头走 n - move - 1 步；它的后继就是新头。断开后，链表从新头出发仍恰好经过原来的 n 个节点一次。

解题步骤

  1. 空链表、单节点或 k == 0 时直接返回。
  2. 一次遍历得到链表长度 n 和原尾节点。
  3. 计算 move = k % n；若为 0，链表无需变化。
  4. 令原尾指向原头形成环，从原头走 n - move - 1 步找到新尾。
  5. 先保存 newHead = newTail.next，再断开 newTail.next，返回新头。

例如 [1,2,3,4,5]、k = 2：新尾是第 5 - 2 = 3 个节点 3，从 3 后断开，得到 [4,5,1,2,3]。

代码实现

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;
        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
    stepsToNewTail := length - move - 1
    newTail := head
    for i := 0; i < stepsToNewTail; i++ {
        newTail = newTail.Next
    }
    newHead := newTail.Next
    newTail.Next = nil
    return newHead
}

复杂度分析

  • 时间复杂度：$O(n)$。求长度和定位新尾各至多遍历链表一次，与 k 的大小无关。
  • 空间复杂度：$O(1)$。只使用常数个指针和整数变量。

关键点总结

  • 先用 k % n 消除无效的整圈旋转。
  • 成环后只剩「找新尾、断开」两个动作，指针关系最清楚。
  • 新尾位置要按节点序号推导：第 n - move 个节点，从头走 n - move - 1 步。
  • 面试时应主动说明：先保存新头，再断环，否则会丢失返回入口。

易错点总结

  • 空链表未提前返回：求长度或取模时会空指针或除零。
  • 新尾多走一步：[1,2,3,4,5]、k = 2 会错误地从 4 后断开，得到只右移 1 位的结果。
  • 先断链再读取新头：newTail.next 已变成 null，会丢失新头。
  • 成环后忘记断开：如 [1,2]、k = 1 会返回 2→1→2... 的环形链表。

相似题目

题目 难度 考察点
19. 删除链表的倒数第 N 个结点 中等 同样定位倒数第 k 个节点，但用快慢指针一趟完成
面试题 02.02. 返回倒数第 k 个节点 简单 只需定位不需重接指针，是本题定位环节的简化版
141. 环形链表 简单 本题主动成环，该题反过来检测链表中是否存在环
142. 环形链表 II 中等 不仅判环还要定位入环点，考察环上位置的数学推导
92. 反转链表 II 中等 同为区间级指针重排，考察断开与重接的顺序控制