Reverse Nodes In k-Group Problem Solution

Reverse Nodes In k-Group 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:

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

Reverse Nodes In k-Group Problem Solution

Problem Solution In Python

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy_head=M_head=ListNode()
        dummy_head.next=head
       # Calculate Length
        l=0
        t=head
        
        while t:
            l+=1
            t=t.next
            
        # Get multiple length of k
        l//=k
        
        while head and l:
            
            for _ in range(1,k):
                
                temp=head.next
                head.next=temp.next
                temp.next=M_head.next
                M_head.next=temp
                
            if head:
                M_head,head=head,head.next
            l-=1
        return dummy_head.next

Problem Solution In Java

public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return head;
        ListNode tail = head;
        int movements = k;
        while(tail != null && movements > 1){
            tail = tail.next;
            movements--;
        }
        if(tail == null) return head;
        
        ListNode next = tail.next;
        tail.next = null;
        ListNode newHead = reverse(head);
        head.next = reverseKGroup(next, k);
        return newHead;
    }
    public ListNode reverse(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode nextTemp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextTemp;
        }
        return prev;
    }

Problem Solution In C++

class Solution {
public:
    
    ListNode* reverse(ListNode* head) {
        if(head==NULL || head->next==NULL)
            return head;
        ListNode* temp=reverse(head->next);
        ListNode* newHead=temp;
        while(temp->next!=NULL)temp=temp->next;
        temp->next=head;
        head->next=NULL;
        return newHead;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k==0 || head==NULL || head->next==NULL)
            return head;
        int cnt=k-1;
        ListNode* tmp=head;
        while(cnt && tmp->next!=NULL){
            tmp=tmp->next;cnt--;
        }
        if(cnt!=0)
            return head;
         ListNode* t=reverseKGroup(tmp->next,k);
        tmp->next=NULL;
         ListNode* newHead=reverse(head);
        tmp=newHead;
        while(tmp->next!=NULL)
            tmp=tmp->next;
        tmp->next=t;
        return newHead;
        
        
    }
};

Problem Solution In C

struct ListNode* kSteps(struct ListNode* head, int k) {
    for (int i = 1; i < k && head; i++)
        if (head) head = head->next;

    if (head) return head;
    return NULL;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    if (k < 2) return head;
    struct ListNode* prev = kSteps(head, k);
    if (prev) {
        struct ListNode* next = head, * curr = head, * tail = curr;
        head = prev;
        prev = prev->next;
        for (int i = 0; i < k; i++) {
            next = next->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        while (prev = kSteps(curr, k)) {
            tail->next = prev;
            tail = curr;
            prev = prev->next;
            for (int i = 0; i < k; i++) {
                next = next->next;
                curr->next = prev;
                prev = curr;
                curr = next;
            }
        }
    }
    return head;
}