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

使用递归可以解决这个问题。

1. 将链表按照K为分界线，分成左右两个链表。
2. 右边的链表进行递归处理，再次分割。当右边的数量小于k时不再进行分割。
3. 左边的链表进行翻转，翻转后将head与右边的链表相连

时间复杂度O(n) 空间复杂度O(1)

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
        if(head==null || head.next==null){
            return head;
        }
        
        // 把链表分成左右两个链表，右边的链表进递归行翻转
        int i = 0;
        ListNode temp = head;
        while(temp!=null && i<k) {
            temp = temp.next;
            i++;
        }
        if(i<k){
            // 如果链表的长度小于k，不翻转
            return head;
        }
        // 递归翻转右侧的链表
        temp = reverseKGroup(temp, k);
        // 翻转左侧的链表
        ListNode pre = null;
        ListNode curr = head;
        ListNode next = null;
        i = 0;
        while(curr!=null && i<k) {
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
            i++;
        }
        // 此时head作为左侧链表的最后一个，连接右边的链表
        head.next = temp;
        return pre;
    }
}