旋转链表

题目

题目来源：力扣（LeetCode）

给你一个链表的头节点 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 * 109

思路分析

记给定链表的长度为 size，我们注意到当向右移动的次数 k ≥ size 时，我们只需要向右移动 k % size 次即可。因为每 size 次移动都会让链表变为原状。这样我们可以知道，新链表的最后一个节点为原链表的第 (n - 1) - (k % size) 个节点。

这样，我们可以先将给定的链表连接成环，然后再将指定的位置断开。

在具体代码中，我们首先计算出链表的长度 size ，然后找到该链表的末尾节点，将其与头节点相连，这样就得到了闭合为环的链表。

然后我们找到新链表的最后一个节点，即原链表的第 (size - 1) - (k % size) 个节点，将当前闭合为环的链表断开，即可得到我们所需要的结果。

特别地，当链表长度不大于 1 ，或者 k 为 size 的倍数时，新链表将与原链表相同，我们无需进行任何处理。

var rotateRight = function (head, k) {
    if (k === 0 || !head || !head.next) {
        return head;
    }
    // 定义 cur 指针，指向链表头节点
    let cur = head;
    // 获取链表的长度
    let size = length(head);
    // 获取原链表的尾节点
    while (cur.next) cur = cur.next;
    // 将原链表连接成环，此时变成了一个新的链表
    cur.next = head;
    // 获取新链表的最后一个节点，即原链表的第 (size - 1) - (k % size) 个节点
    let add = size - k % size - 1;
    for (let i = 0; i < add; i++) {
        head = head.next;
    }
    // 此时的 head 为新链表的最后一个节点，通过 head.next 获取新链表的头节点
    cur = head.next;
    // 将新链表的尾节点的 next 指针置为 null，即在新链表的尾节点处将环断开
    head.next = null;
    // 断开后的环就是我们需要的结果
    return cur;
};
// 计算链表的长度
const length = function (head) {
    let size = 1;
    let temp = head;
    while (temp.next){
        temp = temp.next;
        size += 1;
    }
    return size;
}

/