Placement

Leet Code : Reverse Nodes in k-Group Java, Python ,C++ JavaScript 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:

Source :Leetcode
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]

C++ Solution

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:
void reverse(ListNode s,ListNodee){
ListNode *p=NULL,*m=s, *n=s->next;
while(p!=e){
m->next = p;
p=m;
m=n;
if(n!=NULL)
n= n->next;

 }
}
ListNode* reverseKGroup(ListNode* head, int k)
{
if(head == NULL || k==1|| head->next == NULL)
{
return head;
}
ListNode* dummy = new ListNode(-1);
dummy->next=head;
ListNode *bf = dummy,*e=head;

     int count=k-1,i=0;
     
     // ListNode *s=head,*e=head;
     while(e!=NULL)
     {   
         i++;
         if(i%k==0){
             ListNode *s= bf->next,*temp=e->next;
             reverse(s,e);
             bf->next=e;
             s->next = temp;
             bf=s;
             e=temp;
             
         }
         else{
             e=e->next;
         }
     }
 return dummy->next;
}

};

Java Solution :

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int n = 0;
        ListNode temp = head;
        while(temp!=null){
            n++;
            temp = temp.next;
        }
        int times = n / k;
        
        temp = null;
        ListNode current = head, prev = null, nextL, start;
        
        for(int i = 0; i< times; i++){
            
            start = current;
            // prev = current;
            // current = temp;
            
            
            for(int j = 0; j<k ; j++){
                nextL =  current.next;
                current.next = prev;
                prev = current;
                current = nextL;
                
            }
            // temp = current;
            start.next = current;
            if(temp == null){
                head = prev;
                temp = start;
            }
            else{
                temp.next = prev;
                temp = start;
                
            }
            prev = start;
            
            
            
        }
        // prev.next = null;
        return head;
    }
}

Python Solution :

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverse(self,head):
        prev=None
        pres=head
        fut=head.next
        while pres:
            pres.next=prev
            prev=pres
            pres=fut
            if fut:
                fut=fut.next
        return prev,head
    
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        ptr=head
        fir=None
        while ptr:
            val=k
            sec=ptr
            while val>1:
                sec=sec.next
                if not sec:
                    return head
                val-=1
            temp=sec.next
            sec.next=None
            h,t=self.reverse(ptr)
            if fir:
                fir.next=h
            else:
                head=h
            t.next=temp
            fir=t
            ptr=temp
        return head
Facebook
Twitter
LinkedIn

Leave a Comment