Reverse Nodes in k-Group | Among the toughest problems of LinkedList

[@takeUforward]

Doing 1-1 interactions on every Sunday or Monday on Instagram Live, do join :) Insta: instagram.com/striver_79/

[@saharamanson1970]

​@@takeUforward U r right let them throw trash from their mouth... you are awesome bro.. and last thing I always see add in your channel

[@manikanth.8507]

I think we have to assign dummy->next to kth Node.

[@saurabhkumarkaushal469]

@@manikanth.8507 No its correct because both pre and dummy reference are initially pointing to same dummy ListNode object and after first iteration dummynode object -> next will be pointing to kth node of first group (kth node means that node which was at kth position in that group before reversing).

[@stuartYoung559]

Guys don`t worry if u are not able to understand in 1 or 2 or more times. . its really a pointer complex problem.. give it proper time. its gonna help you in many problems with reversing enrolled in

[@Ace-ex9gg]

This question was really crazy. I don't know what type of intution im gonna tell the interviewer. Like if people solved this question by them selves then you are really cool. And im gonna be like you one day.

[@dhruvkaran9724]

took me 1.5 hours to fully understood this but believe me it's my believe in you that force me to watch it again and again that u must have taught good and once I understood my god it is.......... :D

[@jambajuice07]

guys you dont need to remember this , try out recursion its way easier than this , and interviewers also expect recursive solution. iterative way is just complicated : here's my recursive code: class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { // recursive function to reverse first k nodes // base case if(head == NULL) return NULL; // if elements are less than k then we will return head; int count =0; ListNode* prev = NULL; ListNode* next = NULL; ListNode* curr = head; while(curr!= NULL and count next; } if(countnext = prev; prev = curr; curr=next; count++; } // recurse for next group if(next!= NULL){ head->next = reverseKGroup(next , k); } return prev; } };

[@vishakhas1867]

To break it down at 8:36 was super cool. Btw appreciate your hard work sir:)

[@pranav288]

accent lol

[@somparnachakrabarti5616]

My take on how dummy->next is pointing to new head. Initially dummy and pre are referencing the same address so any change made to pre->next will also be reflected in dummy->next but after reversing the first group pre is assigned to a complete new address. Therefore changes made to pre later do not affect the dummy->next as the latters job was over after first reversal itself.

[@raghavmittal5982]

thanks for this i was confused about this

[@rishabladha6831]

Thanks man !

[@gandhijainamgunvantkumar6783]

Thank you so much. I was confused about this and I watched the video 3 times still not understood, how dummy->next is returning head. Thanks for making it clear

[@namansharma5128]

acc to ur concept, he has made curr and nex also point to dummy , then why only pre is effecting it???????

[@namansharma5128]

samajh nai aa rha ......can explain plzzzzzzz???????? how pre is changing the node to which dummy points.

[@harshvardhansingh9202]

There is lot of confusion between dummy node and the pointers . You have taken "next" as a pointer? And "curr", "pre" as a dummy node ?

[@saketmehta6697]

Just in case, if you are looking for recursive approach which is way easier than this: Algo: 1 Check if our current set has k elements 2 If k elements are not present then we don't have to reverse, directly return head (base case) 3 Reverse the current set elements before going inside next set recursion 4 While coming back from recursion call set the current set head to next prev 5 Check and dry run code for better understanding! class Solution { public ListNode reverseKGroup(ListNode head, int k) { int count = 0; ListNode curr = head; // to check - if set is having more than k elements , otherwise return head while (count != k) { if (curr == null) { return head; } curr = curr.next; count++; } // to find reverse if we have k elements in set curr = head; ListNode prev = null; count = 0; ListNode next = null; while (count != k) { next = curr.next; curr.next = prev; prev = curr; curr = next; count++; } //assign head of this set to next set prev if (next != null) { head.next = reverseKGroup(next, k); } return prev; } }

[@amitbhattacharya356]

Awesome explanation. Was stuck with this problem for more than 3 hours. Very clear and crisp explanation. Saved my day. Thanks.

[@invinciblearmyvlogsshorts7911]

I always thought linked list is scoring , but after solving this one, i am

[@alistair0111]

I was asked this question in an interview and I fumbled a lot because I tried recursion. This solution is way simpler and easy.

[@preetkatiyar969]

which company

[@alistair0111]

@@preetkatiyar969 it was for a startup called thinkify labs

[@LEO-ds7pe]

Recursion was way easier

[@cr7johnChan]

@@LEO-ds7pe would not you need O(N) space for recursion with O(N) time ?

[@willturner3440]

After watching it 3times , I understand😉

[@karanverma5924]

+1 😂😂

[@dakshkalucha5408]

I thought I am the only one 😢

[@scorcism.]

my record 4 times

[@aesthetic_vibes_404]

My record 3 days

[@hariniexplains8351]

@@aesthetic_vibes_404 guess I'm gonna break it ☠️

[@zealkapadiya1096]

Thankyou for a different approach! Interviewbit provided a recursive approach for this question which ig isnot good! Again thanks!

[@takeUforward]

Glad you enjoyed it!

[@rohitgpt7201]

yeah, they provided a different approach, and their end result is also different, coz in their solution, if remaining nodes is less than k, it will reverse them also, so if the question comes with that part included, their solution is very good and easy to understand, the leetcode's question is different from that and in my opinion that makes it slightly difficult to understand...

[@zealkapadiya4783]

@@rohitgpt7201 Okay thankyou for the information

[@sans.creates]

@@rohitgpt7201 exactly!

[@nikhilkumar-24]

@@takeUforward bhaiya,, how dummy node will only travel with us until 1st Kth groups reverse operation in the code given in video, at first we initialise dummy =head then where we have updated dummy that we can return dummy.next;

[@allwell8570]

I had tried this problem several times, but was unable to do it .I have been following SDE sheet since last few days. And this time without even watching video I solved this problem.

[@jaihari1404]

uses of dummy: dummy chapter closes after 1st k-group reverse(at end of reverse there may situation that arise that last ele in 1st Kth group reverse operation will be head) and i should track that head, for that i am using dummy so that i can return dummy.next atlast. Note: dummy node will only travel with us until 1st Kth groups reverse operation. after we reversed 1st kth group dummy stay there itself pointing next to our head. uses of prev:prev is used to connecting node backward.(connecting nex to its previous node by using prev[nex.next=prrev.next]) uses of nex: is used to connecting node backward(read prev uses) uses of curr:used to connect Kth group last nodes next node(next kth group starting node).

[@nikhilkumar-24]

how dummy node will only travel with us until 1st Kth groups reverse operation in the code given in video, at first we initialise dummy =head then where we have updated dummy that we can return dummy.next;

[@NoahDevSd]

Great video....I understood it after watching the video twice and dry running the code by myself ❤

[@yoda6994]

Getting better and better every day!

[@om_1_2]

Just great bro. I tried everytime this problem but the way u explained, thanks a lot bro.

[@takeUforward]

Glad it helped

[@rohanpareek6720]

thank you bhai, for this one 😍, mazaaaaa aagaya🔥 GOD BLESS YOU!!!

[@arifwaqas698]

Where did we point dummy->next to node 3 ???

[@aandz6194]

Just tell us why you wrote next->next = pre->next ...........instead of "cur" ...... You supposed to tell but you forgot.

[@sjoshi1363]

On 8:28, curr is a different node and pre's next is the node, where we have to connect the nex's next.

[@venkateshnagumantri3130]

i had completly done this using a general reverse linked list pattern. here is my code in python. class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: n=0 curr = head while curr!=None: n+=1 curr = curr.next count=0 tr=head curr=head while count0: fwd=curr.next curr.next=pre pre=curr curr=fwd temp-=1 if count==1: head=pre else: tr.next=pre tr=p tr.next = curr return head

[@dennyage4791]

wow,i sloved it by myself, feeling proud

[@adityaagarwal2324]

I bet no one can remember the process after 2-3 days of learning it.

[@code-a-mania4100]

Awsm!!😄 Striver Sir aka bhaiya!!

[@satyamsrivastava.]

8:35 so you just break it thown... That was cool

[@deepaliraghuvanshi9775]

also "last node" @16:48 😂😂

[@AinasDiaries]

@@deepaliraghuvanshi9775 exactly whats with that accent?? ;))

[@nikhilnagrale]

I was also going to comment the same

[@nirajgusain1452]

5:59 "so whot we gonna follow".

[@rajnandini9862]

@@nirajgusain1452 instead of focussing on his accent, i think you should focus on his way of explaining the problem and approch..that will help you in future not his accent.

[@himanshudhaka5149]

Super happy I solved in 1st attempt without solution. Thanks.

[@Patrick_08]

Great explanation Buddy. Learning new and efficient approach every day. Thanks for everything @striver 🔥.

[@freshcontent3729]

can you tell me the logic if in case in this question i also wanted the end ( the left out parts in this case 7->8) also to be reversed ? what change would i need to make in the code for this case ? please reply

[@aniketbhoite7168]

@@freshcontent3729 u can use same reversing logic...just the number of reversing ptrs will be less than k-1 .....it will be n%k ....

[@priteshchavan4580]

explaining this method to interviewer is a task itself

[@settyruthvik6236]

#code inn python class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: # @param A : head node of linked list # @param B : integer # @return the head node in the linked list def reverseList(self,head,k): dummy=ListNode(0) dummy.next=head curr=head count=0 while curr: count+=1 curr=curr.next prev=dummy curr=dummy while(count>=k): curr=prev.next nextn=curr.next for i in range(k-1): curr.next=nextn.next nextn.next=prev.next prev.next=nextn nextn=curr.next prev=curr count=count-k while count

[@art4eigen93]

Well, I did this solution in an interview and the interviewer said this will not gonna work and did not let me do a dry run and ended the interview. I am still finding out what went wrong.

[@rishabh1620]

Thank u so much guruji , great explaination 💗💗

[@vvsish8803]

Python: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if head is None or k==1: return head dummy=ListNode(0) dummy.next=head pre=cur=nex=dummy count=0 while cur.next: count+=1 cur=cur.next while count>=k: cur=pre.next nex=cur.next for i in range(1,k): cur.next=nex.next nex.next=pre.next pre.next=nex nex=cur.next count-=k pre=cur return dummy.next

[@sanyam_18]

Hey buddy can you help me in one thing In the code you have used ---> for i in range(1,k): And I've used ----> while i

[@shashanksinghal8395]

A much easier approach. Start counting. Once you reach k, pass that particular part to the reverse operation. Here’s the code for it. Uncomment the print statements it you want to understand the code. It is accepted on leetcode as well. With time complexity O(2N) a space complexity is O(1). Sorry for strange variable names. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverse_ll(self, l1): if not l1.next: return temp start_node = l1 prev = l1 l1 = l1.next prev.next = None while l1: #print("l1 inside:", l1) temp = l1.next l1.next = prev prev = l1 l1 = temp return prev, start_node def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: l1 = head #hash_map = {} temp = l1 n = 1 i = 0 prev = None reversed_linked = l1 while l1: l1 = l1.next n += 1 #print("n and l1: ",n, l1) if n == k and l1: n = 1 # print("hash_map inside",hash_map) temp2 = l1.next l1.next = None temp3,start_node = self.reverse_ll(temp) # print("reversed_ll:",reversed_linked) if not prev: reversed_linked = temp3 else: prev.next = temp3 prev = start_node # print("start node and temp inside:",temp3, start_node) #hash_map[i] = temp3 l1 = temp2 temp = l1 i += 1 if temp and prev: #hash_map[i] = temp prev.next = temp # print(hash_map) return reversed_linked

[@learner_1228]

Sir, is it important to consider the dummy node?

[@InderjitSingh-sh9ve]

Simple jo reverse a ll ka code hai vahi hai bs add a condition of count

[@pranavkorhale5089]

I spend my 6 hr to solve this question and Pass a few test cases. yes its the toughest problem of linked list.

[@muskanmittal1029]

Hey please could someone tell me why pre->next instead of cur

[@shadabmalik5785]

not getting the part where you return dummy->next as new head.... as initially you assign dummy->head, so how dummy->next update

[@abhishekseth7187]

I found recursive solution comparatively easier to understand, here's the code- int countNodes(Node* head) { int count = 0; while (head) { count++; head = head->next; } return count; } Node* kReverse(Node* head, int k) { // Write your code here. if (!head || k next; current->next = prev; prev = current; current = next; count++; } // Link the reversed group to the next reversed group if (next) { head->next = kReverse(next, k); } return prev; }

[@DCAP-rm6dj]

Nice but this wouldn't be optimal considering you are taking extra space for those recursive calls making S.C as O(n) instead of O(1)

[@jineshsalot6213]

Brilliant, just brilliant!! Amazing Explanation

[@codemachine7381]

This is converted to leetcode easy after your explanation..

[@its_me_hb]

I must say you are a genius.. Because I am still feeling it really tough

[@harshitgupta3393]

I have thought of another approach for this. I thought to first to find Linked List which is needed to be reversed in O(K) and then reverse that list in O(K) and finally point start and end points of reversed List appropriately and continue with this until we reach the end. Is this a good approach to tell to the interviewer if I don't tell him this approach?

[@nipunaggarwal7568]

Plz show your approach's code.

[@tushargogiya4017]

I have also tried this approach but im not getting correct answer can you show your code

[@harshitgupta3393]

@@tushargogiya4017 @Nipun Aggarwal my approach is tedious please follow the approach given in the video. I had to try it many times to make the code work but not worth it.

[@rishabhgupta9846]

@@tushargogiya4017 ListNode *reverse(ListNode *head) { if (head == NULL or head->next == NULL) { return head; } ListNode *newHead = reverse(head->next); head->next->next = head; head->next = NULL; return newHead; } ListNode *reverseKGroup(ListNode *head, int k) { ListNode *front = head, *tail = head, *next = head; ListNode *newHead = new ListNode(0), *prevtail = newHead; while (1) { tail = next; front = next; for (int i = 0; i < k - 1 and tail; i++) { tail = tail->next; } if (tail == NULL) { break; } next = tail->next; tail->next = NULL; ListNode *temp = reverse(front); prevtail->next = temp; while (temp and temp->next) { temp = temp->next; } prevtail = temp; } prevtail->next = front; return newHead->next; }

[@curs3m4rk]

if k = 3 and there are two nodes remaining at last, what should i do to rotate those 2 nodes as well

[@sans.creates]

@@SanjaySingh-xw3mi she asks if we have to !

[@freshcontent3729]

@@sans.creates can you tell me the logic if in case in this question i also wanted the end ( the left out parts in this case 7->8) also to be reversed ? what change would i need to make in the code for this case ? please reply

[@freshcontent3729]

did u find ?

[@parthsalat]

Thanks! By drawing it on paper, I understood it quickly!

[@niravgusai6718]

I think the recursive approach is easy to understand, But you did it well !!

[@freshcontent3729]

can you tell me the logic if in case in this question i also wanted the end ( the left out parts in this case 7->8) also to be reversed ? what change would i need to make in the code for this case ? please reply

[@niravgusai6718]

@@freshcontent3729 in every recursive call , calculate length of LL. If k>length just return the list, else next recursive call.

[@sachinvishwakarma6322]

recursive code in JS var reverseKGroup = function(head, k) { let n = 0; let current = head; while(current !== null) { n++; current = current.next; } return reverse(head, k, n); }; function reverse(head, k, n) { let prev = null; let curr = head; let next = null; let count = 0; if (!head || !head.next) { return head; } if (n

[@jambajuice07]

@@freshcontent3729 ``` class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { // recursive function to reverse first k nodes // base case if(head == NULL) return NULL; // if elements are less than k then we will return head; int count =0; ListNode* prev = NULL; ListNode* next = NULL; ListNode* curr = head; while(curr!= NULL and count next; } // if(countnext = prev; prev = curr; curr=next; count++; } // recurse if(next!= NULL){ head->next = reverseKGroup(next , k); } return prev; } }; ``` hey this should work if you want to reverse even if the length

[@sanskarsharma5408]

C++ code is wrong because when I try to implement it in leetcode output is same as input.

[@shanthiyasekar7317]

sir can you explain that how come dummy next point to the new modified list?

[@saikumargatla4706]

Initially pre,cur,nex=dummy any changes made in pre will also affect dummy. But after the line cur=pre->next,nex=nex-> and pre=cur they aye pointing to completely different nodes rather than dummy. So after these lines dummy remains unchanged .I am I correct can anyone who has understood ans

[@yashveernathawat8154]

pre is dummy node or dummy pointer i mean pre->next will be different in these two cases...kind of confused.😕

[@guptaparas]

can anyone please explain last line of the code, how come dummy->next has the head of updated list

[@omi_naik]

Thanks Really Great Explanation!! Drawing on paper was easy to understand

[@arpitdas2530]

How is the address in dummy pointer changing??? We are not changing its value so it should always point to 1 only?

[@freshcontent3729]

did u find the answer ? i have same doubt

[@prabhaaa8208]

Those who want to reverse the remaining group(next = head; node* curr = dummy , *prev=dummy,*nxt=dummy; int count = 0; while(curr->next){ curr=curr->next; count++; } while(count>1){ //modify condition curr=prev->next; nxt = curr->next; for(int i = 1 ; inext = nxt->next; nxt->next = prev->next; prev->next = nxt; nxt = curr->next; } prev = curr; count-=k; } return dummy->next; } //for variable size groups given in array //b -> array contains the sizes of each group //k - size of array b Node *getListAfterReverseOperation(Node *head, int k, int b[]){ if (head == NULL) return head; Node* dummy = new Node(0); dummy->next = head; Node* curr = dummy; Node* prev = dummy; Node* nxt = dummy; int count = 0; while (curr->next) { curr = curr->next; count++; } int j = 0; while (count > 1 && jnext; nxt = curr->next; if (b[j] == 1) { prev = curr; count--; j++; continue; }else if(b[j]==0){ j++; continue; } for (int i = 1; i < std::min(count, b[j]); i++) { curr->next = nxt->next; nxt->next = prev->next; prev->next = nxt; nxt = curr->next; } prev = curr; count -= b[j]; j++; } return dummy->next; } 👍👍👍

[@anmol3]

Are we not allowed to use recursion in interviews?

[@_-6912]

Hi Striver, the dummy's reference is always the head which was 1 in the example. Now, the pre reference was changing but not dummy's as the reference was always to head that is 1. I did not understand how the dummy's reference is changed to Node 3 in example which is the new head. Could you kindly explain once?

[@sanskarsharma5408]

Yes you are right because of that it showing output same as input

[@adarshdubey1784]

No bro u r taking it wrong .. firstly prev is referencing to dummy that means if u r doing prev.next= something then dummy is start referencing to another nodes and after execution of loop 1st time, as u can see in code (prev=curr) that means now henceforth if u do something like prev.next then it won't make any effect on dummy ... So, Conclusion is dummy only change in first iteration .

[@freshcontent3729]

@@adarshdubey1784 can you tell me the logic if in case in this question i also wanted the end ( the left out parts in this case 7->8) also to be reversed ? what change would i need to make in the code for this case ? please reply

[@adarshdubey1784]

@@freshcontent3729 I think for that u have to run the loop count(in this case count will become 2 because it is decreasing by k ) time... And u have prev , u have curr... start applying logic of reverse linkedlist... In simple words ... U just reverse the remaining linkedlist and after that connects it to prev node ...I might not sound clear but this part is easy u just watch editorial on Gfg ,u will get the intuition 👍

[@freshcontent3729]

@@adarshdubey1784 i didnt get it , can you please make the changes in strivers code ? i would be grateful

[@sathwikabhignan1862]

Just Wow!! what an explanation sir

[@vikasgupta6701]

I found the recursive way to reverse this very intuitive compared to the iterative one

[@v.sreesairam9488]

understood bhaiya thank you very much :)

[@alexrcrew1975]

why we are not performing normal reverse technicque ?

[@chandraprakashyadav8090]

The dummys next was head ,ie 1 initially , after doing all the reversal , we are returning dummys next ie 1 , but now the new head should be 3 , I have this doubt , can anyone help

[@takeUforward]

Do a dry run once to get stuffs cleared..

[@ithcaironsthlotron5546]

Which one to tell in interview, this or the recursive one

[@deathsgameplay2680]

Can't we just swap the value of first node and last , like this and last would be null for later section

[@dayashankarlakhotia4943]

Very good explanation understood in one hour

[@SachinGoswami-d7i]

//here is recursive solution of this problem. int get_length(Node* head){ int count = 0; Node* temp = head; while(temp != NULL){ count++; temp = temp->next; } return count; } Node* reverse(Node* head, int k, int length){ //base case if(length < k){ return head; } Node* temp = head; int count = 0; while(I < k){ temp = temp->next; I++; } length = get_length(temp); Node* prev = NULL; Node* curr = head; Node* forward = NULL; while(curr != temp){ forward = curr->next; curr->next = prev; prev = curr; curr = forward; } //recursive call Node* reverseNode = reverse(temp, k,length); head->next = reverseNode; return prev; }

[@ShubhamMahawar_Dancer_Actor]

I think one change required when you are calculating length of instead of cur->next!=NULL it should be cur!=NULL

[@takeUforward]

Given code works fine.. has been tested and then explained..

[@gautamsuthar4143]

He is counting from dummy node that's why the condition should be cur->next!=NULL. If it was head node then the condition would be cur!=NULL.

[@ShubhamMahawar_Dancer_Actor]

@@gautamsuthar4143 yea yes right and thanks for clearing ✌️

[@freshcontent3729]

@@gautamsuthar4143 can you tell me the logic if in case in this question i also wanted the end ( the left out parts in this case 7->8) also to be reversed ? what change would i need to make in the code for this case ? please reply

[@a.techsys9389]

I kept the same condition as striver did ,just initialize/start the with count =1 ;

[@sharankarchella2688]

For the First group reversing can we do without creating dummy ? correct me if I am wrong ?

[@crosswalker45]

we can.. But handling the edge cases would be a tedious job without the dummynode

[@shashankojha3452]

Great Job brother❤💙✨

[@RajeevCanDev]

solution without using dummy node :- int getLen(Node* head){ int len=0; while(head!=NULL){ head=head->next; len++; } return len; } Node* kReverse(Node* head, int k) { if(head == NULL || head->next == NULL){ return head; } if(getLen(head) >= k){ Node* curr=head; Node* prev=NULL; Node* next=NULL; int cnt =0; while (curr != NULL && cnt < k) { next = curr->next; curr->next = prev; prev = curr; curr = next; cnt++; } if (next != NULL) head->next = kReverse(next, k); return prev; } else return head; }

[@shikharathaur6664]

Wonderful explanation !!

[@freshcontent3729]

can you tell me the logic if in case in this question i also wanted the end ( the left out parts in this case 7->8) also to be reversed ? what change would i need to make in the code for this case ? please reply

[@kaichang8186]

understood, thanks for the great explanation

[@vetiarvind]

i've seen this in an amazon interview..kind of hard to get it on the whiteboard.

[@adarshdubey1784]

So, were u able to solve it completely or partially ?

[@freshcontent3729]

can you tell me the logic if in case in this question i also wanted the end ( the left out parts in this case 7->8) also to be reversed ? what change would i need to make in the code for this case ? please reply

[@arpitpachauri9189]

@@freshcontent3729 ptr1=prev->next; if(ptr1!=NULL) ptr2=ptr1->next; while(ptr2 && l){ ptr1->next=ptr2->next; ptr2->next=prev->next; prev->next=ptr2; ptr2=ptr1->next; l--; } you have to write this extra code for the nodes that are left below the above code. here ptr1 is curr pointer , ptr2 is nex pointer, l is the count and prev is the pre pointer.

[@jayajmire6779]

Correct me if I am wrong, I think there is problem when size of LinkedList and K both are equal . you need to add one more condition.

[@ashishshahpur7105]

It will not be a problem. The condition in the while loop already is checking for count >= k, so even if count is equal to k it will work

[@udayjordan4262]

i would tell to not follow this because what if the question comes the last element i mean the element except the k you have to reverse it so basic way of reversal a LL should be maintained so better to use recursion.check this code below only change the base case or edge case ListNode* reverse(ListNode *head,int k,int c){ ListNode *previous = NULL; ListNode *curr= head; ListNode *n ; if(cnext=reverse(n, k,c-k); } return previous; } ListNode* reverseKGroup(ListNode* head, int k) { int d=0; ListNode* curr=head; while(curr!=NULL){ curr=curr->next; d++; } return reverse(head,k,d); } };

[@pulkitjain5159]

What is the intution behind the approach , i mean reccursive solution has an intution but this solution is hard to get

[@priyanshukoshta2307]

Solution Using Stack class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { if(k==1 || head->next==NULL) return head; ListNode *temp, *cur=head, *first; temp = new ListNode(); stack s; bool flag=true; while(cur!=NULL) { s.push(cur); cur = cur->next; if(s.size()==k) { while(s.size()) { temp->next = s.top(); temp = temp->next; if(flag==true) { first = temp; flag = false; } s.pop(); } temp->next = cur; } } return first; } }; we are using first pointer just get the starting pointer

[@TheVR7]

Thanks, bro, your explanation is always helpful.!!!!!1

[@anmolagarwal5952]

Recursive & easier solution: Reverse first k nodes, then do a recursive call. If there is less than k nodes at end, then re-reverse it to its original form; ListNode* reverse(ListNode* head){ ListNode* prev = NULL; ListNode* next = NULL; while(head != NULL){ next = head->next; head->next = prev; prev = head; head = next; } return prev; } ListNode* reverseKGroup(ListNode* head, int k) { int i = k; ListNode* prev = NULL; ListNode* curr = head; ListNode* next = NULL; while(i && curr != NULL){ next = curr->next; curr->next = prev; prev = curr; curr = next; i--; } if(i) return reverse(prev); head->next = reverseKGroup(curr, k); return prev; }

[@GauravKumar-dw2ml]

your solun is consuming O(n) space recursively.

[@art4eigen93]

I think this is a well-known solution but not the optimized one. But every interviewer is seeking this solution rather than what Striver explained. Don't know why. Got rejected once because the Interviewer could not understand the Striver's solution and told me I made a simple thing complicated, LOL!

[@rituraj6056]

pair reversek(node* head,int k) {node* p=head,*q=head; for(int i=1;inext; p->next=NULL; } else if(q) { node* r=q->next;q->next=p;p=q;q=r; } } pairres={p,q}; return res; } struct node *reverse (struct node *head, int k) { node*r=head; // Complete this method pairres=reversek(head,k);node*p=res.first,*q=res.second; node* head1=p; while(q) { res=reversek(q,k); node *r1=q; p=res.first,q=res.second;r->next=p;r=r1; } return head1; } //time complexity O(N) and space O(1)

[@letsexplore7590]

bhaiya eagerly waiting for your tree series.

[@Anujkumar-wt1qs]

Count should be initialized with 1 for counting the the length of LinkedlList

[@takeUforward]

We start with dummy node if you carefully observe, so it works!!

[@Anujkumar-wt1qs]

@@takeUforward yup, got it.

[@laxminarayanchoudhary939]

Converting the list into Cylic linked list was nice...

[@freshcontent3729]

can you tell me the logic if in case in this question i also wanted the end ( the left out parts in this case 7->8) also to be reversed ? what change would i need to make in the code for this case ? please reply

[@ritikashishodia675]

Bhaiya agr is q m each k groups ko reverse krke arrange kre to tb bhi n m hoga

[@freshcontent3729]

can you tell me the logic if in case in this question i also wanted the end ( the left out parts in this case 7->8) also to be reversed ? what change would i need to make in the code for this case ? please reply

[@arpitpachauri9189]

ptr1=prev->next; if(ptr1!=NULL) ptr2=ptr1->next; while(ptr2 && l){ ptr1->next=ptr2->next; ptr2->next=prev->next; prev->next=ptr2; ptr2=ptr1->next; l--; } you have to write this extra code for the nodes that are left below the above code. here ptr1 is curr pointer , ptr2 is nex pointer, l is the count and prev is the pre pointer.

[@akshat2819]

Reversing k nodes and then recursively call for next won't be a good solution?

[@sakshamgupta1667]

Recursive stack will increase space complexity

[@freshcontent3729]

@@sakshamgupta1667 can you tell me the logic if in case in this question i also wanted the end ( the left out parts in this case 7->8) also to be reversed ? what change would i need to make in the code for this case ? please reply

[@AdityaKumar-be7hx]

Here's a modified version of what striver is doing (I think) class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { if(head==nullptr || head->next==nullptr || k==1) return head; int length = getLength(head); ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* curr=nullptr, *prev=nullptr, *forward=nullptr; ListNode* startOfGroupHead = head; ListNode* endOfPrevGroup = dummy; while(length>=k){ curr=startOfGroupHead; prev=endOfPrevGroup; int cnt=0; // reverse the k nodes while(cntnext; curr->next=prev; prev=curr; curr=forward; ++cnt; } startOfGroupHead->next=curr; // last head should be pointing to the next head endOfPrevGroup->next=prev; // the end of last group should be pointing to the head of new groud which is prev endOfPrevGroup=startOfGroupHead; // the new end will be the previous groups head (before reversing) startOfGroupHead=curr; // for the next iteration length=length-k; } return dummy->next; } int getLength(ListNode* head){ int len=0; while(head!=nullptr){ head=head->next; ++len; } return len; } };

[@sumit49]

I cant understand how dummy head is pointing to 3.plese help

[@crosswalker45]

by assigning the prev.next = curr.next.next

[@namansharma5128]

why returning dummy-> next ???????? how is dummy changing......plzz don't tell that pre is changing it. then why dummy is changing due to pre.......curr and nex pointers are also pointing to dummy

[@sachinrajput4536]

8:35 break it down, comes with an accent😂

[@ashwinvarma9349]

After a long time!

[@shrutishreya7773]

What an explanation!!!!!!!!!!!!!

[@rudrapreeyam]

why you are putting nex -> next = pre -> next instead of curr You said that you will tell us later. But you missed telling us why. Could you try to answer the question when it arises?

[@vaibhavmurarka5179]

I have an On complexity solution and ig this one is easier to understand. basically, i reverse the current k elements after the kth elements. and in case if the length is multiple of k then there is a check for that ListNode* rev(ListNode* head) if(head==NULL||head->next==NULL){ return head; } ListNode*newhead=rev(head->next); head->next->next=head; head->next=NULL; return newhead; } ListNode* reverseKGroup(ListNode* head, int k) { if(k==0||k==1){ return head; } if(head==NULL||head->next==NULL){ return head; } ListNode*cur=head; ListNode*prev=NULL; ListNode*oldhead=head; ListNode*oldheadprev=NULL; int i=0; while(cur!=NULL){ if((i%k==0)&&(cur!=head)){ if(oldhead==head){ prev->next=NULL; ListNode*newhead=rev(oldhead); head=newhead; oldhead->next=cur; oldheadprev=oldhead; oldhead=cur; }else{ prev->next=NULL; ListNode*newhead=rev(oldhead); oldheadprev->next=newhead; oldhead->next=cur; oldheadprev=oldhead; oldhead=cur; } }else{ if(((i+1)%k==0)&&cur->next==NULL){ if(oldhead==head){ ListNode*newhead=rev(oldhead); oldhead->next=NULL; return newhead; }else{ ListNode*newhead=rev(oldhead); oldheadprev->next=newhead; oldhead->next=NULL; } cur=NULL; continue; } } prev=cur; cur=cur->next; i++; } return head; }

[@lifeisfun4863]

While using your code in leetcode/gfg, getting same issue"Runtime error- segmentation fault" . Please explain bhaiya!!!

[@lifeisfun4863]

Sorry, I got my mistake I was running the loop from 0 instead of 1.

[@nileshsinha7869]

thank you soo much sir. Really appreciate what u are doing. will it too much to ask for some tips to deal with procrastination, bcz i'm doing a lottt

[@parthsalat]

Find a reason to live/work. For more information watch the movie, "The Shawshank Redemption"

[@senpaikun5947]

How to get the main method for this for his code

[@sahillodha6084]

Understood it in 7th or 8th attempy 😂 💖

[@K_EC_AnuragKumarMishra]

Bro ur way of explaining is awesome. Thanks a lot

[@lakshmiprasanna7058]

Understood 💯💯💯