Reverse Nodes in k-Group LeetCode Solution

Last updated on January 20th, 2025 at 10:51 pm

Here, we see the Reverse Nodes in k-Group LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Linked List

Companies

Facebook, Microsoft

Level of Question

Hard

Reverse Nodes in k-Group LeetCode Solution

Reverse Nodes in k-Group LeetCode Solution

1. 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 the nodes themselves may be changed.

Reverse Nodes in k-Group ex1
fig-1
Example 1: (fig-1)
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Reverse Nodes in k Group
fig-2
Example 2: (fig-2)
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “In-place Reversal of a LinkedList”. This pattern involves reversing parts of a linked list in-place without using extra space for another data structure. The problem specifically focuses on reversing nodes in groups of size k.

3. Code Implementation in Different Languages

3.1 Reverse Nodes in k-Group C++

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* temp=head;
        for(int i=0;i<k;i++){
            if(!temp)return head;
            temp=temp->next;
        }
        
        ListNode *prev=NULL;
        ListNode *nex1=NULL;
        temp=head;
        for(int i=0;i<k;i++){
            nex1=temp->next;
            temp->next=prev;
            prev=temp;
            temp=nex1;
        }
        if(nex1!=NULL)
            head->next=reverseKGroup(nex1,k);
        return prev;        
    }
};

3.2 Reverse Nodes in k-Group Java

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
    ListNode prev = null;
    ListNode current = head;
    int count = 0;
    ListNode next = null;
	
    //reverse blindly
    while (current != null && count < k) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
        count++;
    }

    //restoring if count lesser
    if (count < k) {
        current = prev;
        prev = null;
        next = null;
		
        while (count != 0) {
            count--;
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
    }
    if (next != null) {
        head.next = reverseKGroup(next, k);
    }
    return prev;        
    }
}

3.3 Reverse Nodes in k-Group JavaScript

var reverseKGroup = function(head, k) {
    return reverseAGroup(head);
    
    function reverseAGroup(start) {
        let temp_k = k;
        let curr = start;
        while(curr && temp_k-- > 0) {
            curr = curr.next;
        }
        if(temp_k > 0) {
            return start;
        }
        const groupTail = start, 
              groupHead = reverse(start, curr); 
        
        if(curr) {  
            groupTail.next = reverseAGroup(curr); 
        }
        return groupHead; 
    }
    function reverse(root, nextGroup) {
        let curr = root,
            next = null,
            prev = null;
        
        while(curr && curr !== nextGroup) {  
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev; 
    }    
};

3.4 Reverse Nodes in k-Group Python

class Solution(object):
    def reverseKGroup(self, head, k):
        l, node = 0, head
        while node:
            l += 1
            node = node.next
        if k <= 1 or l < k:
            return head
        node, cur = None, head
        for _ in xrange(k):
            nxt = cur.next
            cur.next = node
            node = cur
            cur = nxt
        head.next = self.reverseKGroup(cur, k)
        return node

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n)O(n/k)
JavaO(n)O(n/k)
JavaScriptO(n)O(n/k)
PythonO(n)O(n/k)
  • The time complexity is O(n) for all implementations because every node is visited exactly once during the reversal process.
  • The space complexity is O(n/k) due to the recursion stack. This is because the function is called recursively for each group of size k, and there are approximately n/k groups.
  • The reversal is done in-place, meaning no additional data structures are used to store the reversed nodes, which keeps the space complexity low apart from the recursion stack.
Scroll to Top