[路飞]_leetcode-61-旋转链表

「这是我参与11月更文挑战的第2天，活动详情查看：2021最后一次更文挑战」

[题目地址][B站地址]

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

我们来看一下下面这张图：

当我们把链表连成环的时候，如果 k 为 1，我们只需要在4节点的位置把环解开，返回头节点即可

如果 k 为2，我们只需要在3节点的位置把环解开，返回头节点即可

所以本题的解题思路如下：

1. 根据给定题意，链表可能为空，k 可能为0，所以我们要特判一下如果链表为空或者k=0，直接返回头节点即可
2. 获取链表长度 len，如果 k是 len 的整数倍，那么我们其实是不需要对链表进行翻转的，否则将 k 对 len 取余，即我们需要翻转的次数
3. 将链表连成环
4. 找到拆环的位置，获取拆环后的头节点，然后拆环，返回头节点即可

这里有一个问题就是我们需要在哪里拆环呢？

上面我们讲过 k 为1和2的时候我们分别需要在4节点和3节点的位置拆环，根据这个规律，我们可以得出拆环位置为之前链表的尾结点向后走 len-k 步之后的节点位置。

以下是代码实现：

var rotateRight = function(head, k) {
    // 特判
    if(head === null || k === 0) return head;
    // 获取链表长度
    let cur = head,len = 1;
    while(cur.next){
        cur = cur.next;
        len++;
    }
    // k 如果为长度整数倍，无需操作
    if(!(k %= len)) return head;
    // 连成环
    cur.next = head;
    // 找到拆环位置
    let num = len-k;
    while(num){
        cur = cur.next;
        num--;
    }
    // 拆环前拿到拆环后头节点
    const res = cur.next;
    // 拆环
    cur.next = null;
    return res;
};
复制代码

至此，我们就完成了leetcode-61-旋转链表

如有任何问题或建议，欢迎留言讨论！