LeetCode #25: Reverse Nodes in k-Group

Hello, coding enthusiasts! Today, we’re solving the “Reverse Nodes in k-Group” problem from LeetCode. This problem is a great exercise in linked list manipulation and recursion.

We’re given a linked list and a number k, and we need to reverse the nodes of the list k at a time. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

The catch is that we can’t modify the values in the list’s nodes, only the nodes themselves may be changed.

Let’s dive into the problem!

Problem Statement

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:

Reverse Nodes in k-Group ex-1 — Source: LeetCode

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

Reverse Nodes in k-Group ex-2 — Source: LeetCode

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

Approach

The problem can be solved using a recursive approach. Here are the steps:

Base Case: If the list is empty or has less than k nodes, we return the list as it is.
Reverse k Nodes: We reverse the first k nodes of the list.
Recursive Call: We make a recursive call to the rest of the list and attach it to the end of the reversed list.
Return New Head: Finally, we return the new head of the list.

Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the list. This is because we are processing each node exactly once.

Space Complexity

The space complexity is O(n), due to the recursive stack. In the worst case, the depth of the recursive call stack will be n/k, which is O(n).

Code

Python

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # Base case
        node = head
        for _ in range(k):
            if not node:
                return head
            node = node.next
        
        # Reverse k nodes
        prev, curr = None, head
        for _ in range(k):
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        
        # Recursive call to the rest of the list and attach it to the end of the reversed list
        head.next = self.reverseKGroup(curr, k)
        
        # Now the head is the last node of the reversed list
        return prev

JavaScript

var reverseKGroup = function(head, k) {
    // Base case
    let node = head;
    for (let i = 0; i < k; i++) {
        if (!node) {
            return head;
        }
        node = node.next;
    }
    
    // Reverse k nodes
    let prev = null;
    let curr = head;
    for (let i = 0; i < k; i++) {
        let nextNode = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextNode;
    }
    
    // Recursive call to the rest of the list and attach it to the end of the reversed list
    head.next = reverseKGroup(curr, k);
    
    // Now the head is the last node of the reversed list
    return prev;
};

Conclusion

In this post, we tackled the “Reverse Nodes in k-Group” problem from LeetCode. We used a recursive approach to reverse the nodes in k-group.

The time complexity of this approach is O(n), and the space complexity is also O(n) due to the recursive stack.

Happy coding!

Learn More: