题解 | #链表中的节点每k个一组翻转#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
         *
         * @param head ListNode类
         * @param k int整型
         * @return ListNode类
         */
        public ListNode reverseKGroup (ListNode head, int k) {
            // write code here
            ListNode q = null;

            q = findEnd(head,k);

            if(q == head || q == null) {
                // 说明不够k个
                return head;
            }
            // 最后一个节点的一下一个节点
            if(q.next == null) {
                // 说明正好k个
                ListNode h = ReverseList(head);
                head.next = null;
                return h;
            }
		  // 递归获取下一个链表
            ListNode b = reverseKGroup(q.next,k);
            q.next = null;
            // 翻转k个节点 - 只有q.next == null 的情况下才能做单向链表旋转，当然这块可以单独拿出来，也可以与当前的业务想结合，循环到q结尾就不再做单向链表旋转。这块使用了之前的单向链表旋转。
            ListNode h = ReverseList(head);
		  // head 原来是头，现在是尾部
            head.next = b;
            return h;
        }

        // 找到k个节点的末尾 如果不够k个 返回头节点
        public ListNode findEnd(ListNode h,int k){
            ListNode x = h;
            for(int i = 0;i < k-1;i++) {
                if(h == null) {
                    // 说明不够k个
                    return x;
                }
                h = h.next;
            }
            return h;
        }

        // 单向链表翻转
        public ListNode ReverseList(ListNode head) {
            if(head == null ||  head.next == null){
                return head;
            }

            ListNode p=head;
            ListNode q=null;

            while(p.next !=null ){
                p = head.next;
                head.next = q;
                q = head;
                head = p;
            }
            head.next = q;
            return head;

        }
    
}