Reverse Nodes in k-Group | Leetcode 25 solution

on

 25. Reverse Nodes in k-Group | Leetcode Solution



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


Solution :




/**
 * 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* solve(ListNode* head, int k , int cnt)
    { 
        if(cnt < k )
        {
            return head;
        }
        if(head  == NULL )
        {
            return head;
        }
        int t =0;
        ListNode* curr = head;
        ListNode* pre = NULL ;
        ListNode* nex = NULL;
        ListNode* x =NULL;
         while(cnt >= k && t < k )
         { 
            if(t == 0)
             {
                 x = curr;
             }
             nex = curr ->next;
             curr ->next = pre;
             pre = curr;
             curr = nex;
             t++;
         }
         x ->next =  solve(curr  , k, cnt - k);
         return pre;

    }
    ListNode* reverseKGroup(ListNode* head, int k) {

         ListNode* temp = head;
         int cnt = 0;
         while(temp != NULL)
         {
             cnt++;
             temp = temp->next;
         }
        return solve(head , k , cnt);
  

    }
};



Comments

Post a Comment