25. Reverse Nodes in k-Group

LeetCode

这个问题具有递归性质，原问题是"对于一整条链表，翻转k-group”，子问题是“对于除去已翻转的部分，翻转k-group”。

我们可以分几步解决这个问题：

  1. 翻转以head开头的前k个节点（区间翻转）
  2. 递归调用reverseKGroup，将第k + 1个元素作为head
  3. 拼接前两部分
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // reverse [begin, end)
    private ListNode reverse(ListNode begin, ListNode end) {
        ListNode prev = null;
        ListNode curr = begin;
        while (curr != end) {
            ListNode oldNext = curr.next;
            curr.next = prev;
            prev = curr;
            curr = oldNext;
        }
        return prev;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode fast = head, slow = head;
        // if this group is smaller than k,
        // then we don't have to reverse this group
        for (int i = 0; i < k; i++) {
            if (fast == null) {
                return head;
            }
            fast = fast.next;
        }
        ListNode newHead = reverse(slow, fast);
        slow.next = reverseKGroup(fast, k);
        return newHead;
    }
}