题解 | #牛群旋转#java

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 (head == null || head.next == null || k == 0) {
            return head;
        }

        int len = 1; // 链表长度
        ListNode tail = head; // 尾节点

        // 找到尾节点并计算链表长度
        while (tail.next != null) {
            len++;
            tail = tail.next;
        }

        // 首尾相连形成环
        tail.next = head;

        k = k % len; // 处理k大于链表长度的情况

        // 找到需要断开的位置
        ListNode newTail = head;
        for (int i = 0; i < len - k - 1; i++) {
            newTail = newTail.next;
        }

        // 断开环，得到新的头节点
        ListNode newHead = newTail.next;
        newTail.next = null;

        return newHead;
    }
}

• 首先处理特殊情况，如果链表为空、只有一个节点或者旋转次数为0，则直接返回原链表。
• 通过遍历链表找到尾节点并计算链表长度。接下来，将尾节点与头节点相连，形成一个环。
• 对于旋转次数 k，如果 k 大于链表长度，则取 k 除以链表长度的余数。
• 需要找到需要断开的位置。通过遍历找到新的尾节点，即原头节点的前一个节点。
• 断开环，将新的尾节点的 next 指针设为 null，并返回新的头节点。

通过这种方法，可以实现链表的旋转，时间复杂度为 O(n)，其中 n 是链表的长度。

该题考察的知识点是链表的操作和旋转。

具体涉及到的知识点包括：

1. 链表的基本结构和操作：链表由节点组成，每个节点包含一个值和指向下一个节点的指针。常见的链表操作有遍历、插入、删除等。
2. 旋转链表：旋转链表即将链表中的节点向右移动 k 个位置。这里需要注意处理旋转次数大于链表长度的情况。旋转链表可以通过修改指针的方式来实现。