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

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
        ListNode hair = new ListNode(0), cur = hair, next = null, p = head;
        hair.next = head;
        while (true) {
            for (int i = 0; i < k; i++) {
                if (p == null) return hair.next;
                p = p.next;
            }
            next = cur.next;
            if ((cur.next = reverseK(cur.next, k)) == next) break;
            cur = next;
        }
        return hair.next;
    }
    private ListNode reverseK(ListNode head, int k) {
        ListNode p = null, cur = head, next;
        while (k-- > 0) {
            next = cur.next;
            cur.next = p;
            p = cur;
            cur = next;
        }
        head.next = cur;
        return p;
    }
}

1、首先可以考虑实现对一个链表的前 k 项进行翻转

• 基本思路是：定义一个虚拟头节点 p，用于遍历链表的指针 cur 和 指针 next，循环开启：
• 先用 next 记录 cur 的下一个节点，
• 借住 p 将 cur 指向翻转，即 cur.next = p;
• 接着，p 向后移即 p = cur，cur 向后移即 cur = next
• 循环出来后，p 就是翻转之后的链表头节点
• 这里需要注意的是，对于前 k 项翻转，最后的 cur 指向到了原链表的第 k+1 个节点，而 head 的指向此时是 null，因此需要将 head 接到 cur 上即 head.next = cur，否则仅仅翻转了链表的前 k 项，后续链表节点会丢失

2、借助前 k 项翻转的实现方法，再进行 k 个一组的翻转实现

• 基本思路是：定义一个虚拟头节点 hair，并将 hair.next = head，定义 cur 指向 hair
• 定义一个 p 指针，用于判断链表剩余的节点个数是否足够 k 个，如果不够，说明后续节点不需要翻转，可以直接返回结果了
• 如果足够，那么对前 k 项进行翻转
• 这里做了一个特殊判断，即如果翻转后的节点等于next，表示没有翻转，即 k = 1，可以提前结束