Leetcode刷题 | 第110题：旋转链表

为什么要担心？如果努力了，担心不会让结果变得更好。

61. 旋转链表^[1]

题目：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

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

示例 2：输入：head = [0, 1, 2], k = 4，输出：[2, 0, 1]

提示：链表中节点的数目在范围 [0, 500] 内，-100 <= Node.val <= 100，0 <= k <= 2 * 10^9

---

分析：设链表的长度为 cnt，实际上，仅需要向右移动 move = k % cnt 次即可。那么，链表将从索引 n - 1 - move 后断开，后半段的最后一个指针将指向前半段的首位置。为了完成上述操作：

1. 计算链表的长度 cnt，计算过程中记录最后一个指针的地址 last；
2. 根据索引 n - 1 - move 定位前半段最后一个位置和后半段的首位置；
3. 前半段的最后一个位置指向 null；
4. 后半段的最后一个指针 last 指向前半段的首位置 head；
5. 后半段的首位置地址，即为旋转链表的头结点。

注意1：当 k = 0, k = cnt 或者 k % cnt == 0 时，旋转链表与原链表相同，无需处理。

注意2：（思路）也可以先将给定的链表连接成环，然后将指定位置断开。

JAVA代码：

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        int cnt = 0, move;
        ListNode dummy = head;
        ListNode last = null; // 原链表的最后一个位置
        while (dummy != null) {
            if (dummy.next == null) last = dummy;
            dummy = dummy.next;
            ++cnt;
        }
        move = k % cnt; // 实际需要移动的次数
        if (move == 0) return head;
        ListNode early_head = head;
        for (int i = 0; i < cnt - move - 1; i++) early_head = early_head.next;
        ListNode later_head = early_head.next;
        // System.out.println(later_head.val);
        early_head.next = null;
        last.next = head;
        return later_head;
    }
}

• 时间复杂度为O(N)；空间复杂度为O(1)。

参考资料

[1]

旋转链表: https://leetcode-cn.com/problems/rotate-list/