题解 | #牛群旋转#

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
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        
        ListNode ans = head;
        int n = 0;
        ListNode curr = head;
        //找到总数n
        while (curr != null) {
            curr = curr.next;
            n++;
        }
        //找到需要断节的地方
        int m = n - (k % n) - 1;
        ListNode temp = head;
        while (m > 0) {
            temp = temp.next;
            m--;
        }
        ans = temp.next;
        temp.next = null;
        //移动到最后
        ListNode temp2 = ans;
        while (temp2.next != null) {
            temp2 = temp2.next;
        }
        //将最后的拼接到最前面
        temp2.next = head;
        return ans;
    }
}

考察的知识点：

链表，反转

解题思路：

实际需要我们做的就是将后面的k个节点反转到最前面，k可能大于n，所以k = k % n。

首先我们找到链表总结点数n，前面一段节点数量就是n - k，后面一段就是k。

将head保存后，遍历移动到n - k - 1节点的位置后，将后面节点开始处定义为ans保存，遍历到链表的最后，将最后节点的next指向head完成反转，返回ans。