25. Reverse Nodes in k-Group
Tags: leetcode
Published: 2023-06-03 16:09:09

Problem source: [25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/description/)

<strong>1. Understand the problem</strong>
This problem is an advanced version of reversing a linked list.
In order to solve this one, we need to understand how to traverse a linked list and how to reverse one.

<strong>2. Notice the constraints</strong>

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7yub8jyq5kz4pv9mxnvu.jpg)

Here, pay attention that k could be 1. In that case, it just means the list will not be modified at all. 
So, what we can do when k == 1 is:
```java
if (k == 1) return head;
```

<strong>3. First thought</strong>
The easiest solution that we can immediately think of is to store all the nodes into an array list. Then we can just swap the node in k-group. Then go through the list and establish a new linked list.

This can be implemented easily so I will not show the code here.
However, this solution requires an extra O(n) space to stores the nodes.

What if we want O(1) space?

<strong>4. Final solution</strong>
We can use recursion.
If we know the length of the linked list is n and the value of k, there are n / k groups that need to reversed.

In general, we can apply a simple recursion using this pseudo code:
1. Get the `tail` of the current sequence (this will help determine the head of the next group - called `next-head`)
2. Reverse the current group and get the `tail` of the modified sequence.
3. Reverse the group starting with `next-head`
4. Link the tail to the new `next-head` (the next head after reversed)
5. Return the current head of the sequence

Based case for this:
- We keep track of a counter showing how many groups remained to be reversed, if the counter = 0, no reverse is needed.

Here is the code:
```java
/**
 * 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 int getListLength(ListNode head) {
        ListNode current = head;
        int result = 0;
        while (current != null) {
            result ++;
            current = current.next;
        }
        return result;
    }

    public ListNode recursion(ListNode head, int k, int counter) {
        if (counter == 0) {
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        ListNode nextHead = new ListNode(-1);
        // need to determine the next head first. 
        // do this while reversing is possible
        ListNode tail = head;
        ListNode current = head;
        for (int i = 0; i < k; i++) {
            if (i == k - 1) {
                // we have reached the tail and can determine the next head. 
                nextHead = current.next;
            }
            // in general, reverse the list;
            ListNode next = current.next;
            current.next = dummyHead.next;
            dummyHead.next = current;
            current = next; 
        }

        // call reverse for next head;
        ListNode newNextHead = recursion(nextHead, k, counter - 1);
        
        // linked with the tail
        tail.next = newNextHead;

        return dummyHead.next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) {
            return head;
        }

        // 1. count the length of the list
        int listLength = getListLength(head);

        // 2. calculate the counter 
        int counter = listLength / k;

        // 3. start the recursion
        return recursion(head, k, counter);
    }
}
```