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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        if (head == null){
            return null;
        }

        //求链表长度
        ListNode temp = head;
        int len = 0;
        while (temp != null){
            len++;
            temp = temp.next;
        }
        if (k == 1){
            return head;
        }

        //solve
        ListNode newHead = null;
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = head;
        ListNode tailTrack = head;
        for (int i = 0; i < len; i += k){
            int count = 0;
            while (count < k){
                if (cur != null){
                    count++;
                    pre = cur;
                    cur = cur.next;                    
                }
                else{
                    break;
                }          
            }
            if (count == k){
                //将链断干净，保证反转的这个链表链表结尾是null，否则会将整条链表都给直接反转
                pre.next = null;
                if (i == 0){
                    newHead = reverse(tailTrack);
                }
                else{
                    reverse(tailTrack);
                }
            }
            //剩余的链表末尾段长度不够k个不翻转，直接连接即可,此时已经获得了完整的符合题意的链表结构，直接退出循环
            if (count < k){
                tmp.next = tailTrack;
                break;
            }
            //第一轮tmp不动，先让tailTrack动，然后再进行操作，起到保存的作用
            if (i != 0){
                tmp.next = pre;
                tmp = tailTrack;
            }
            tailTrack = cur;
        }
        return newHead;
    }

    //反转链表
    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = cur.next;
        while (next != null){
            cur.next = pre;
            pre = cur;
            cur = next;
            next = cur.next;
        }
        cur.next = pre;
        return cur;
    }
}