0025. Reverse Nodes in k-Group

https://leetcode.com/problems/reverse-nodes-in-k-group

Description

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

**Input:** head = [1,2,3,4,5], k = 2
**Output:** [2,1,4,3,5]

Example 2:

**Input:** head = [1,2,3,4,5], k = 3
**Output:** [3,2,1,4,5]

Example 3:

**Input:** head = [1,2,3,4,5], k = 1
**Output:** [1,2,3,4,5]

Example 4:

**Input:** head = [1], k = 1
**Output:** [1]

Constraints:

• The number of nodes in the list is in the range sz.

• 1 <= sz <= 5000

• 0 <= Node.val <= 1000

• 1 <= k <= sz

Follow-up: Can you solve the problem in O(1) extra memory space?

ac1: non-recursive

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // validate remain nodes > k
        // cut k nodes
        // reverse it
        // dummy
        // loop, remain, cut, ranger, step

        // corner case
        if (head == null || head.next == null || k <= 1) return head;

        ListNode dum = new ListNode(0);
        ListNode d = dum;

        while (head != null) {
            ListNode cut = head, ranger = head;
            int step = 1;
            // walk
            while (ranger.next != null && step < k) {
                ranger = ranger.next;
                step++;
            }
            // validate
            if (step < k) break;
            // cut nodes
            head = ranger.next;
            ranger.next = null;
            // add to dum
            d.next = reverse(cut);
            while (d.next != null) d = d.next;
        }

        // add the remain
        d.next = head;

        return dum.next;
    }

    private ListNode reverse(ListNode cut) {
        ListNode prev = null;
        while (cut != null) {
            ListNode tmp = cut;
            cut = cut.next;
            tmp.next = prev;
            prev = tmp;
        }
        return prev;
    }
}