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

import java.util.*;

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

public class Solution {
    /**
     * 递归解决，每k个一组
     * 函数定义：将head为头结点的链表，按照k个一组反转，
     * 每组只负责自己这个组的反转，递归结束条件，不够k个一组
     * （注意：反转后，头变尾，尾变头）
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        ListNode ptr = head;
        int i;
        for(i=0; i<k-1; i++) {
            if (ptr == null) {
                break;
            }
            ptr = ptr.next;
        }
        //不够k-1步或者ptr为null不够k个
        if (i < k-1 || ptr == null) {
            return head;
        }
        ListNode next = ptr.next;
        ptr.next = null;
        reverseList(head);
        //head是反转后的尾巴
        head.next = reverseKGroup(next, k);
        //ptr是反转后的头
        return ptr;
    }
    //链表反转
    public ListNode reverseList(ListNode head) {
        ListNode res = null;
        ListNode curr = head;
        while(null != curr) {
            ListNode next = curr.next;
            curr.next = res;
            res = curr;
            curr = next;
        }
        return res;
    }
}