25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

Categories:

算法

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

     public ListNode reverseKGroup(ListNode head, int k) {

        // 基本判断

        if (head == null || k == 1) return head;

        // 计算当前组的长度是否够k个节点

        ListNode curr = head;

        int count = 0;

        while (curr != null && count < k) {

            curr = curr.next;

            count++;

        }

        // 如果不够k个节点，保持原有顺序

        if (count < k) return head;

        // 递归处理后续节点组

        curr = reverseKGroup(curr, k);

        // 翻转当前组的k个节点

        ListNode prev = curr;

        ListNode now = head;

        while (count > 0) {

            ListNode next = now.next;

            now.next = prev;

            prev = now;

            now = next;

            count--;

        }

        return prev;

    }

}