LeetCode Problem – Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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]

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Java Solution

class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
    }
}

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

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prevGroupEnd = dummy;

        int count = 0;
        ListNode current = head;

        // Count the number of nodes in the list
        while (current != null) {
            count++;
            current = current.next;
        }

        while (count >= k) {
            ListNode groupStart = prevGroupEnd.next;
            ListNode groupEnd = groupStart;

            // Reverse k nodes in the current group
            for (int i = 1; i < k; i++) {
                ListNode nextNode = groupEnd.next;
                groupEnd.next = nextNode.next;
                nextNode.next = groupStart;
                groupStart = nextNode;
            }

            prevGroupEnd.next = groupStart;
            prevGroupEnd = groupEnd;

            count -= k;
        }

        return dummy.next;
    }

    // Helper method to print the linked list
    public void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        int k1 = 2;

        ReverseKGroup solution = new ReverseKGroup();
        ListNode result1 = solution.reverseKGroup(head1, k1);
        System.out.print("Example 1 Output: ");
        solution.printList(result1);

        // Example 2
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);
        head2.next.next.next.next = new ListNode(5);
        int k2 = 3;

        ListNode result2 = solution.reverseKGroup(head2, k2);
        System.out.print("Example 2 Output: ");
        solution.printList(result2);
    }
}

This program defines a ListNode class representing a node in the linked list and a ReverseKGroup class with the reverseKGroup method to reverse the nodes in groups of size k. The printList method is a helper method to print the linked list. The main method demonstrates how to use the program with the provided examples.

Python Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class ReverseKGroup:
    def reverseKGroup(self, head, k):
        if not head or k == 1:
            return head

        dummy = ListNode(0)
        dummy.next = head
        prev_group_end = dummy

        count = 0
        current = head

        # Count the number of nodes in the list
        while current:
            count += 1
            current = current.next

        while count >= k:
            group_start = prev_group_end.next
            group_end = group_start

            # Reverse k nodes in the current group
            for _ in range(1, k):
                next_node = group_end.next
                group_end.next = next_node.next
                next_node.next = group_start
                group_start = next_node

            prev_group_end.next = group_start
            prev_group_end = group_end

            count -= k

        return dummy.next

    # Helper method to print the linked list
    def print_list(self, head):
        while head:
            print(head.val, end=" ")
            head = head.next
        print()

# Example usage:
# Example 1
head1 = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
k1 = 2

solution = ReverseKGroup()
result1 = solution.reverseKGroup(head1, k1)
print("Example 1 Output:", end=" ")
solution.print_list(result1)

# Example 2
head2 = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
k2 = 3

result2 = solution.reverseKGroup(head2, k2)
print("Example 2 Output:", end=" ")
solution.print_list(result2)

This Python code mirrors the Java solution. It defines a ListNode class for representing a node in the linked list and a ReverseKGroup class with the reverseKGroup method to reverse the nodes in groups of size k. The print_list method is a helper method to print the linked list. The example usage section demonstrates how to use the program with the provided examples.