Reverse List In K Groups

Here, the getLength function is used to find the remaining nodes and is called each time for recursive. thus finds the remaining nodes whether they are to be reversed or not 

int getLength(Node *temp){

    int cnt=0;

    while(temp != NULL){

        temp = temp->next;

        cnt++;

    }

    return cnt;

}

Node* kReverse(Node* head, int k) {

    int n = getLength(head);   //to get remaining nodes

    //Base case

    if(head==NULL){

        return head;

    }

    Node *prev = NULL;

    Node *curr = head;

    Node *next = NULL;

    int cnt =0;

    while(curr != NULL && cnt<k){

        next = curr->next;

        curr->next = prev;

        prev = curr;

        curr = next;

        cnt++;

    }

//n-k≥ k is done to find whether remaining nodes are to reversed or not

    if(next !=NULL && n-k>=k){    

        head->next = kReverse(next,k);  //calls recursive function 

    }

    else{

        head->next= curr;

    }

    return prev;

}

Node* reverse(Node* head){
    if(head == NULL || head->next ==NULL){
        return head;
    }
    Node* back =NULL;
    Node* curr =head;
    Node* front =NULL;
    while(curr != NULL){
        front =curr->next;
        curr->next =back;
        back =curr;
        curr =front;
    }
    return back;
}

Node *kReverse(Node *head, int k) {
    Node *temp = head;
    Node* nextNode =NULL;
    Node* prevNode =NULL;
    while(temp != NULL){
        Node *kth = temp;
        for(int i=1;i<k && kth != NULL;i++){
            kth =kth->next;
        }
        if(kth == NULL){
            if(prevNode){
                prevNode->next =temp;
            }
            break;
        }
        nextNode =kth->next;
        kth->next =NULL;
        reverse(temp);
        if(head == temp){
            head =kth;
        }
        else{
            prevNode->next =kth;
        }
        prevNode =temp;
        temp =nextNode;
    }
    return head;
}

Added the case where number of elements left ≥ k or else print otherwise.

Made a count function for finding number of elements left or number of forward elements in each recursion.

int count(Node* head){

    int cnt = 0;

    while(head != NULL){

        head = head -> next;

        cnt++;

    }

    return cnt;

}

Node* kReverse(Node* head, int k) {

    if(head == NULL) return head;

    Node* forward = NULL;

    Node* curr = head;

    Node* prev = NULL;

    int cnt = 0;

    while(curr != NULL && cnt < k){

        forward = curr -> next;

        curr -> next = prev;

        prev = curr;

        curr = forward;

        cnt++;

    }

    if(forward != NULL && count(forward)>=k) {

        head->next = kReverse(forward, k);

    }

    else{

        head -> next = forward;

    }

    return prev;

}

Node* kReverse(Node* head, int k) {

    //base case

    if(head == NULL){

        return NULL;

    }

    //step1: reverse the 1st k node

    Node* prev = NULL;

    Node* curr = head;

    Node* next = NULL;

    int count = 0;

    // Check if there are at least 'k' nodes to reverse

    Node* check = head;

    for (int i = 0; i < k; ++i) {

        if (!check)

          return head; // Less than 'k' nodes, return as it is

        check = check->next;

    }

    while(curr != NULL && count < k){

        next = curr->next;

        curr->next = prev;

        prev = curr;

        curr = next;

        count++;

    }

    //step2: recursion call for algorithm 

    if(next != NULL){

        head->next = kReverse(next, k);

    }

    //return haed of reverse call

    return prev;

}

import java.util.* ;
import java.io.*; 
/****************************************************************
    Following is the Linked List node structure

    class Node
    {
    public:
        int data;
        Node next;
        Node(int data)
        {
            this.data = data;
            this.next = NULL;
        }
    };

*****************************************************************/



public class Solution {

	public static Node kReverse(Node head, int k) {
        Node prev=null;
        Node curr=head;
        Node forward=null;
        int count =0;

        while(curr!=null&&count<k)
        {
            forward=curr.next;
            curr.next=prev;
            prev=curr;
            curr=forward;
            
            count++;
        }
        if(count<k){
            return reverse(prev);
        }
         if(forward!=null)
        {
             head.next=kReverse(forward, k);
         }
        return prev;
	}
    private static Node reverse(Node head){
        Node prev=null;
        Node curr=head;
        Node forward=null;
        int count =0;

        while(curr!=null)
        {
            forward=curr.next;
            curr.next=prev;
            prev=curr;
            curr=forward;
        }
        return prev;
    }

}

//count the remainig elements in linked list

int countnum(Node* head){

    int c=0;

    while (head != NULL) {

      head = head->next;

      c++;

    }

    return c;

}

Node* kReverse(Node* head, int k) {

    // Write your code here.

    //if head 

    if(head==NULL)

      {

        return NULL;

      }

    Node* prev=NULL;

    Node* curr= head;

    Node* forward = NULL;

    int count=0;

    while(curr != NULL && count<k)

    {

        forward=curr->next;

        curr->next = prev;

        prev=curr;

        curr=forward; 

        count++;

    }

    int c=countnum(forward);

    if(forward != NULL&& k<=c)

    {

        head->next = kReverse(forward,k);

    }

    else{

       head->next=forward;   

    }

    return prev;

    }

int length(Node *head){

    int i=0;

    while(head!=nullptr){

      head=head->next;

      ++i;

    }

    return i;

}

Node* kReverse(Node* head, int k) {

    if(head==nullptr){

        return head;

    }

   Node *pre=nullptr;

   Node *post=nullptr;

   Node *curr=head;

   int i=0;

  int c=length(head);

  if(c<k){

      return head;

  }

   while(curr!=nullptr && i<k){

       post=curr->next;

       curr->next=pre;

       pre=curr;

       curr=post;

       i++;

   }

   Node *temp=pre;

   while (temp->next != nullptr) {

       temp = temp->next;

   }

   if(curr!=nullptr){

      temp->next=kReverse(curr,k);

   }

   head=pre;

   return head;

}

/**

* Definition for singly-linked list.

* class Node {

* public:

* int data;

* Node *next;

* Node() : data(0), next(nullptr) {}

* Node(int x) : data(x), next(nullptr) {}

* Node(int x, Node *next) : data(x), next(next) {}

* };

*/

Node* kReverse(Node* head, int k) {

// Write your code here.

if(head == NULL || k==0 ){

return head;

}

Node* next = NULL;

Node* curr = head;

Node* prev = NULL;

int i = 0;

//first iteration

int count = 0;

Node*temp = head;

while(temp != NULL){

count++;

temp = temp->next;

}

if(count >= k){

while(curr != NULL && i<k){

next = curr->next;

curr -> next = prev;

prev = curr;

curr = next;

i++;

}

if (next != NULL) {

head->next = kReverse(next, k);

}

return prev;

}else{

return head;

}

}

Node* kReverse(Node* head, int k) {

    // Write your code here.

    if(head == NULL){

        return head;

    }

    Node* ptr=head;

    Node* prev=NULL;

    Node* next=NULL;

    int cnt=0;

    while(ptr!=NULL && cnt < k){

         next=ptr->next;

         ptr->next=prev;

         prev=ptr;

         ptr=next;

         cnt++;

    }

    if(cnt < k){

       ptr=prev;

       prev=NULL;

       next=NULL;

       int cnt=0;

       while(ptr!=NULL && cnt < k){

         next=ptr->next;

         ptr->next=prev;

         prev=ptr;

         ptr=next;

         cnt++;

       }

    }

    if(next != NULL){

        head->next=kReverse(next,k);

    }

    return prev;  

}

int length(Node * head){
    int count=1;
    Node *temp=head;
    while(temp->next!=NULL){
        count++;
        temp=temp->next;
    }
    return count;
}

Node* reversed(Node* &head,int k,int len){
    // Base case
    if (head == NULL || k <= 0) {
        return NULL;
    }
    if(len<k){
        return head;
    }
    
    // Step 1: Reverse first k nodes
    Node* next = NULL;
    Node* curr = head;
    Node* prev = NULL;
    int count = 0;
    
    while (curr != NULL && count < k) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
        count++;
    }
    
    // Step 2: Recursion will handle the rest
    if (next != NULL) {
        head->next = reversed(next, k,len-k);
    }
    
    // Step 3: Return head of reversed list
    return prev;
}

Node* kReverse(Node* head, int k) {
    int len = length(head);
    return reversed(head,k,len);
}