25. Reverse Nodes in k-Group

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

//   Definition for singly-linked list.
// class ListNode {
//     int val;
//     ListNode next;

//     ListNode(int x) {
//         val = x;
//     }
// }

/**
 * Iterative Solution
 *
 * Time Complexity: O(N). Each node is visited twice.
 *
 * Space Complexity: O(1)
 */
class Solution1 {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k <= 1) {
            return head;
        }

        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode leftGrpTail = dummyHead;

        while (true) {
            ListNode grpHead = leftGrpTail.next;
            ListNode current = grpHead;
            ListNode previous = null;
            int count = 0;
            while (current != null && count < k) {
                previous = current;
                current = current.next;
                count++;
            }
            if (count < k) {
                break;
            }

            ListNode rightGrpHead = current;

            // Sperating the current group from right group.
            previous.next = null;

            // Rotate the current group
            current = grpHead;
            previous = null;
            while (current != null) {
                ListNode next = current.next;
                current.next = previous;
                previous = current;
                current = next;
            }

            // After rotating current group
            // previous points to head of current group.
            // grpHead variable points to tail of the current group.
            leftGrpTail.next = previous;
            grpHead.next = rightGrpHead;
            leftGrpTail = grpHead;
        }

        return dummyHead.next;
    }
}

/**
 * Recursive Solution
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(N/k)
 */
class Solution2 {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k <= 1) {
            return head;
        }

        ListNode current = head;
        ListNode previous = null;
        int count = 0;
        while (current != null && count < k) {
            previous = current;
            current = current.next;
            count++;
        }

        if (count == k) {
            previous.next = null;
            ListNode rightSideHead = reverseKGroup(current, k);

            current = head;
            previous = null;
            while (current != null) {
                ListNode next = current.next;
                current.next = previous;
                previous = current;
                current = next;
            }
            head.next = rightSideHead;
            head = previous;
        }

        return head;
    }
}