61.旋转链表

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

示例 1：

img

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

示例 2：

img

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

先成环，然后计算断掉的点

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 特殊情况处理：如果k为0，或链表为空或只有一个元素，则无需旋转，直接返回原头节点
        if (k == 0 || head == null || head.next == null) {
            return head;
        }

        // 计算链表的长度
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        
        // 计算需要移动到头部的元素的个数，n - k % n是因为k可能大于链表长度
        int add = n - k % n;
        
        // 如果add等于n，说明旋转的长度正好是链表的长度，等同于不旋转
        if (add == n) {
            return head;
        }
        
        // 使链表成环
        iter.next = head;
        
        // 找到需要断开连接的位置
        while (add > 0) {
            add--;
            iter = iter.next;
        }
        
        // 新的头节点是iter.next
        ListNode ret = iter.next;
        
        // 断开连接
        iter.next = null;
        
        // 返回新的头节点
        return ret;
    }
}