题解 | #牛群旋转#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode rotateLeft (ListNode head, int k) {
        // write code here  整体思路就是：将倒数k%size个节点移动到头部
        // 1. 处理特殊情况
        if (head == null || head.next == null || k <= 0) return head;

        // 2. 计算链表长度：如果k>链表长度需要进行处理
        int size = 0;
        ListNode cur = head;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        k = k % size;

        // 34.快慢指针找到倒数k+1个节点位置
        ListNode fast = head;
        ListNode slow = head;
        while (k-- != 0) {
            fast = fast.next;
            if (fast == null) return head;
        }

        while (fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 5. 此时slow就是倒数k+1个节点位置，fast就是尾节点的位置
        ListNode h = head; 
        head = slow.next;  // 将头节点指向新的头部
        slow.next = null;  // 将新的尾节点的next置空
        fast.next = h;     // 最后将旧的尾节点接到旧的头节点
        

        return head;

    }
}