力扣经典面试题-旋转链表(Java)

 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]

解题思路

具体来说，我把这道题拆解成了四个关键的步骤。这道题我的大致的理解就是把需要旋转的节点通过头插法放到链表头。

1.获取链表的长度

第一个步骤就是测量链表的长度，举个很简单的例子。比如说我们的链表是[0,1,2]，而k =1那么就是把2这个链表元素旋转到表头那里。那么肯定是要得到链表的长度然后才能找到最后一个元素。然后我们把最后一个元素头插到链表头那里去。于是我们的链表就变成[2,0,1]了。这是其中的一个步骤，整体上也要使用这个思路来解题。

2.计算需要旋转的次数

上面只是说了一个小步骤，但是其实我们这个题需要当成整体来解。什么意思呢，就像第一个例子那样输入：head = [1,2,3,4,5], k = 2那就是旋转两次，那么就是先把5旋转到链表头那里，然后再把4旋转到链表头那里，所以是旋转两次。而且k有可能大于链表的长度，因此有可能需要取模操作。

3.找到需要分割的位置

循环遍历到需要分割的位置，在这里把链表一刀两断，然后重新拼接到链表头。

4.分割链表之后重新连接

这个其实就是我说的头插法，把旋转的链表放到链表头那里。

5.算法的实现（Java）

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null)
            return head;
        ListNode cur = head;
        // 1. 先找到链表的长度
        int length = 0;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        // 2. 计算需要旋转的次数
        k = k % length;
        if (k == 0) {
            return head;
        }

        // 3. 找到需要分割的位置
        cur = head;
        for (int i = 0; i < length - k - 1; i++) {
            cur = cur.next;
        }//找到旋转位置的前一个位置
        // 4. 分割链表并重新连接
        //新的头节点在cur的下一个位置，就是cur之后的节点都要头插法头插到头节点那里去。
        ListNode newHead = cur.next;
        //既然要使用头插法，我们平时一个节点的话很好说，直接尾插就行，但是这是一堆节点，所以就得找到最后一个节点
        //找到最后一个节点然后才能头插

        ListNode tail = newHead;
        
        cur.next = null;
        while (tail.next != null) {
            tail = tail.next;//尾节点遍历到newHead的最后一个节点
        }
        tail.next = head;//头插法
        return newHead;

    }
}