In this post, we are going to solve the 25. Reverse Nodes in k-Group problem of Leetcode. This problem 25. Reverse Nodes in k-Group is a Leetcode hard level problem. Let’s see the code, 25. Reverse Nodes in k-Group – Leetcode Solution.

Problem

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

Now, let’s see the code of 25. Reverse Nodes in k-Group – Leetcode Solution.

Reverse Nodes in k-Group – Leetcode Solution

25. Reverse Nodes in k-Group – Solution in Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    
    public int length(ListNode head){
        ListNode curr = head;
        int len = 0;
        while(curr != null){
            curr = curr.next;
            len++;
        }
        return len;
    }
    
    private ListNode th = null;
    private ListNode tt = null;
    
    private void addFirstNode(ListNode node){
        if(th == null){
            th = node;
            tt = node;
        }
        else{
            node.next = th;
            th = node;
        }
    }
    
    public ListNode reverseKGroup(ListNode head, int k) {
        
        if(head == null || head.next == null || k == 0) return head;
        
        ListNode oh = null;
        ListNode ot = null;
        
        ListNode curr = head;
        int len = length(curr);
        
        while(len >= k){
            int tempK = k;
           
            
            while(tempK-- > 0){
                ListNode forw = curr.next;
                curr.next = null;
                addFirstNode(curr);
               curr = forw;
            }
            
            if(oh == null){
                oh = th;
                ot = tt;
            }else{
                ot.next = th;
                ot = tt;
            }
            
            th = null;
            tt = null;
            len -= k;
        }
        
        ot.next = curr;
        return oh;
    }
}

25. Reverse Nodes in k-Group – Solution in C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head==NULL||k==1) return head;
        ListNode *dummy=new ListNode();
        dummy->next=head;
        ListNode *cur=dummy,*nex=dummy,*pre=dummy;
        int count=0;
        while(cur->next!=NULL){
            cur=cur->next;
            count++;
        }
        while(count>=k){
            cur=pre->next;
            nex=cur->next;
            for(int i=1;i<k;i++){
                cur->next=nex->next;
                nex->next=pre->next;
                pre->next=nex;
                nex=cur->next;
            }
            pre=cur;
            count-=k;
        }
        return dummy->next;
    }
};

25. Reverse Nodes in k-Group – Solution in Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return head
        a = b = head
        for _ in range(k):
            if not b:
                return a
            b = b.next
            
        new_head = self.reverse(a, b)
        a.next = self.reverseKGroup(b, k)
        return new_head
    
    def reverse(self, a, b):
        pre = None
        cur = a
        nxt = a
        while cur != b:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
            
        return pre
        

Note: This problem 25. Reverse Nodes in k-Group is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.