25. Reverse Nodes in k-Group

Problem source: 25. Reverse Nodes in k-Group

1. Understand the problem
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.

2. Notice the constraints

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:

if (k == 1) return head;

3. First thought
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?

4. Final solution
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:

/**
 * 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);
    }
}