LeetCode 补拙笔记

0. 前言

• 日期：2026.05.27
• 题目：61. 旋转链表
• 难度：中等
• 标签：链表、双指针

1. 题目理解

问题描述： 给定一个链表的头节点 head，将链表每个节点向右移动 k 个位置。

示例：

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

2. 解题思路

核心观察

• 链表长度为 n，右移 k 位等价于右移 k % n 位；
• 可以通过找新头、断尾、接原头三步完成原地旋转；
• 也可以用三次反转的思路实现：整体反转 → 反转前k个 → 反转后n-k个。

算法步骤（断尾接合法）

1. 统计链表长度 n，计算实际旋转步数 k = k % n；
2. 找到新尾节点（第 n-k 个节点），其下一个节点即为新头；
3. 断开新尾与新头的连接，将原链表尾节点接回原头节点。

3. 代码实现

package lc0_lc99.lc61;

class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    if (head == null) {
      return head;
    }
    int n = 0;
    ListNode count = head;
    while (count.next != null) {
      count = count.next;
      n++;
    }
    n++;
    if (n == 1) {
      return head;
    }
    k = k % n;
    if (k == 0) {
      return head;
    }
    int headNum = n - k;
    int tailNum = n - k - 1;
    ListNode tail;
    ListNode oldHead = head;

    for (int i = 0; i < tailNum; i++) {
      head = head.next;
    }
    tail = head;
    head = tail.next;
    tail.next = null;
    ListNode last = head;
    while (last.next != null) {
      last = last.next;
    }
    last.next = oldHead;
    return head;
  }

  public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
      this.val = val;
    }

    ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }
}

4. 代码优化说明

减少分支判断，简化逻辑，合并变量声明，代码更紧凑：

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) return null;

        // 统计链表长度
        int size = 0;
        ListNode p = head, tail = null;
        while (p != null) {
            size++;
            tail = p;
            p = p.next;
        }

        // 计算实际旋转步数
        k %= size;
        if (k == 0) return head;

        // 找到新的尾节点（第 size - k 个节点）
        ListNode newTail = head;
        for (int i = 1; i < size - k; i++) {
            newTail = newTail.next;
        }

        // 断尾、接原头
        ListNode newHead = newTail.next;
        newTail.next = null;
        tail.next = head;

        return newHead;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}

5. 复杂度分析

• 时间复杂度：$O(n)$ 统计长度、遍历找新尾节点，均为线性遍历。
• 空间复杂度：$O(1)$ 仅使用常数级额外指针，原地操作。

6. 总结

• 核心思路：统计长度 + 断尾接原头，是旋转链表最直接高效的实现方式；
• 优化后代码减少了冗余变量和分支判断，逻辑更清晰，可读性更高；
• 关键技巧：利用链表的尾节点直接接原头节点，避免了额外的空间开销，实现原地旋转。