Java 题解 | #牛群的重新分组#

该代码考察了链表的分组反转。

需要掌握以下知识点：

• 链表的基本概念和节点的定义
• 链表节点的遍历操作
• 链表节点的插入和删除操作
• 如何将链表分组进行反转
• 使用指针的技巧，如使用多个指针同时操作链表

1. 首先判断特殊情况，如果链表为空或者 k 小于等于 1，则直接返回原链表头节点。
2. 创建一个虚拟头节点 dummy，将其指向链表头节点 head。
3. 初始化两个指针 prev 和 curr，分别指向虚拟头节点和链表头节点。
4. 进行循环，直到无法形成一个完整的长度为 k 的组：使用 getTail 方法获取当前组的尾节点 tail。如果剩余节点不足 k 个，则返回 null。将当前组的头节点 groupHead 和尾节点 tail 分离出来，即将 tail.next 设为 null。调用 reverse 方法翻转当前组的节点。将翻转后的组连接到原链表中。将 prev.next 指向 tail，将 groupHead.next 指向下一个组的头节点 nextGroupHead。更新 prev 和 curr 指针为当前组的头节点 groupHead 和下一个组的头节点 nextGroupHead。
5. 返回虚拟头节点的下一个节点，即为调整后的链表头节点。

在这段修改后的代码中，主要是通过找到每个需要翻转的组的尾节点，将其与前面的部分断开，然后对该组进行翻转，再将翻转后的组与原链表进行连接。最终得到整个链表进行了按照每 k 个节点翻转的效果。

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) {
        if (head == null || k <= 1) {
            return head;
        }

        ListNode dummy = new ListNode(-1);
        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;
    }

    private ListNode getTail(ListNode head, int k) {
        for (int i = 1; i < k; i++) {
            if (head == null) {
                return null;
            }
            head = head.next;
        }

        return 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;
        }
    }

}