How to Reverse Nodes in K-Group in a Linked List?

Reversing nodes in groups of k in a linked list can be a common coding interview question, often asked to assess your understanding of linked lists and your ability to manipulate pointers effectively. This problem can appear complex at first, but through a structured approach, it can be tackled systematically.

The idea behind reversing nodes in k-groups is to take groups of k nodes from the linked list and reverse their order while keeping the overall structure intact. The core challenge lies in managing how you link these groups back together once they have been reversed.

Let’s illustrate this with an example. Consider a linked list represented as follows:

11 -> 2 -> 3 -> 4 -> 5

If we are to reverse this list in groups of k = 2, the expected output should be:

12 -> 1 -> 4 -> 3 -> 5

For k = 3, the output would be:

13 -> 2 -> 1 -> 4 -> 5

To solve this problem, you can follow these steps:

1. Count the number of nodes: First, check how many nodes are in the linked list. This will help you know when you have enough nodes to form a group of k.

2. Reverse the nodes: While traversing the list, if there are at least k nodes remaining, reverse those k nodes.

3. Reconnect the reversed nodes: After reversing, connect the end of the reversed group to the start of the next group.

4. Handle the last group: If there are fewer than k nodes remaining, simply append them to the result without reversing.

Below is a Python implementation of this approach:

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6def reverseKGroup(head: ListNode, k: int) -> ListNode:
7    def reverseLinkedList(head: ListNode, k: int) -> ListNode:
8        prev, curr = None, head
9        while k > 0:
10            next_node = curr.next
11            curr.next = prev
12            prev = curr
13            curr = next_node
14            k -= 1
15        return prev  # New head after reversing
16
17    # Count the total number of nodes
18    count = 0
19    current = head
20    while current:
21        count += 1
22        current = current.next
23
24    # Dummy node to attach the resulting list
25    dummy = ListNode(0)
26    dummy.next = head
27    prev_group_end = dummy
28
29    while count >= k:
30        # Reversed group
31        group_start = prev_group_end.next
32        group_end = group_start
33        
34        # Move group_end to the end of the k-group
35        for _ in range(k - 1):
36            group_end = group_end.next
37
38        # Store the next group
39        next_group_start = group_end.next
40
41        # Reverse the k-group
42        group_end.next = None  # Terminate the current group
43        prev_group_end.next = reverseLinkedList(group_start, k)
44        group_start.next = next_group_start
45
46        # Move previous end to the new end of the reversed group
47        prev_group_end = group_start
48
49        # Reduce the count of remaining nodes
50        count -= k
51
52    return dummy.next

In this solution, we create a helper function reverseLinkedList to handle the actual reversing of k nodes. The main function keeps track of previously processed nodes and efficiently connects the reversed segments back together. This code is structured for clarity, allowing anyone reviewing it to understand the logic behind the node manipulation.