题解 | #牛群的重新分组#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 reverseKGroup (ListNode head, int k) {
        // write code here
        if (head == null || k <= 1) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curr = head;

        while (true) {
            ListNode groupHead = curr;
            ListNode tail = getTail(curr, k);

            if (tail == null) {
                break;
            }

            ListNode nextGroupHead = tail.next;
            tail.next = null;

            reverse(groupHead);

            prev.next = tail;
            groupHead.next = nextGroupHead;

            prev = groupHead;
            curr = nextGroupHead;
        }

        return dummy.next;
    }

    /**
     * 获取以head为头的链表的第k个节点（不包括head本身）。
     *
     * @param head 链表头节点
     * @param k    第k个节点
     * @return 第k个节点的引用
     */
    private ListNode getTail(ListNode head, int k) {
        for (int i = 1; i < k; i++) {
            if (head == null) {
                return null;
            }
            head = head.next;
        }

        return head;
    }

    /**
     * 反转链表。
     *
     * @param head 链表头节点
     */
    private void reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
    }
}

代码考察的知识点：

1. 单链表的遍历和基本操作。
2. 反转链表和链表组的操作。
3. 利用虚拟头节点简化链表操作。

代码解释

1. 定义了一个 LinkedListReverser 类，其中包含了一个名为 reverseKGroup 的方法，用于反转链表中每K个节点的组，保持原始链表顺序不变。
2. 在 reverseKGroup 方法中，首先判断链表是否为空或者组大小是否小于等于1，若是，则直接返回原链表。
3. 创建虚拟头节点 dummy，指向链表的头部，并初始化前一个节点 prev 为虚拟头节点，当前节点 curr 为头节点。
4. 使用 while 循环遍历链表，通过调用 getTail 方法获取每个组的尾节点，并将组内节点进行反转。
5. 更新虚拟头节点的 next 指针，将组内反转后的头节点连接到上一个组的尾节点，同时将组内反转前的头节点连接到下一个组的头节点。
6. 最后返回反转后的链表头部。