Reverse Nodes In K Group - Leetcode Solution

The problem “Reverse Nodes in K-Group” asks us to reverse each group of k nodes in a linked list such that the nodes in a group are linked in reverse order. If the number of nodes in the last group is less than k, we should leave those nodes as they are.

We can solve this problem by following a recursive approach. We’ll use a recursive function that takes the head of a linked list and the value of k as input. The function will reverse the first group of k nodes and call itself recursively for the remaining part of the list. The base condition for the function will be when the list has less than k nodes, in which case we’ll just return the head of the list.

Here's how we can implement this approach:

1. Define the recursive function reverseKGroup(head, k), where head is the head of the linked list and k is the group size.
2. Create a variable called count and initialize it to 0. Also create a variable called current and initialize it to head.
3. Traverse the list using a while loop until the end of the list or until count == k.
4. Inside the loop, increment count and move current to the next node.
5. Check if count == k. If it is, we’ll reverse the current group of k nodes.
6. To reverse the current group, we’ll define a new variable called prev and initialize it to None. Also create a variable called next and initialize it to None.
7. While count > 0, do the following:
   • Set next to current.next.
   • Set current.next to prev.
   • Set prev to current.
   • Set current to next.
   • Decrement count.
8. After reversing the group, set head.next to reverseKGroup(current, k).
9. Return prev as the new head of the reversed group.

Here’s the Python implementation of the recursive approach:

def reverseKGroup(head, k):
    count = 0
    current = head
    while current and count < k:
        current = current.next
        count += 1
    if count == k:
        # Reverse the current group
        prev, next = None, None
        current = head
        while count > 0:
            next = current.next
            current.next = prev
            prev = current
            current = next
            count -= 1
        # Recursively call for rest of the list
        head.next = reverseKGroup(current, k)
        # Return the new head of the reversed group
        return prev
    else:
        # Base case, list has less than k nodes
        return head

That’s it! We’ve successfully solved the “Reverse Nodes in K-Group” problem using a recursive approach.

1