Leetcode-每日一题【61.旋转链表】-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode-每日一题【61.旋转链表】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

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

示例 1：

Leetcode-每日一题【61.旋转链表】

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

示例 2：

Leetcode-每日一题【61.旋转链表】

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

提示：

链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109

解题思路

1.根据题目给出的示例，我们可以看出：将链表中每个节点向右移动K个位置，也就是将链表中倒数第K个节点作为头节点，其前面的所有节点放在原链表尾节点之后。

2.因此整体思路就是找到倒数第K个节点的前一个节点，然后让链表首尾相连，第K个节点作为链表旋转后的新的头节点，其前一个节点作为链表旋转后的尾节点。

3.但是由于k的值可能大于链表长度，因此我们需要先计算一下链表长度，用k对链表长度取余作为我们的新k，否则会空指针异常。

代码实现

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null){
            return head;
        }
       int len = calaulate(head);
       k = k % len;
       ListNode low = head;
       ListNode fast = head;
       for(int i = 1; i <= k; i++){
           fast = fast.next;
       }
       while(fast.next != null){
           low = low.next;
           fast = fast.next;
       }
       fast.next = head;
       head = low.next;
       low.next = null;
       return head;

    }
    private int calaulate(ListNode head){
        int length = 1;
        for(ListNode cur = head; cur.next != null; cur = cur.next){
            length++;
        }
        return length;
    }
}