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

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

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

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.

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.

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 ?

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; } }

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

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

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

After watching it 3times , I understand😉

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.

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

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; } };

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

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).

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

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

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

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

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

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

#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

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

This is converted to leetcode easy after your explanation..

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

Getting better and better every day!

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

Sir, is it important to consider the dummy node?

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

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

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.

explaining this method to interviewer is a task itself

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; }

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

wow,i sloved it by myself, feeling proud

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

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

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

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

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

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

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

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

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.

Thank u so much guruji , great explaination 💗💗

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; } 👍👍👍

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?

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); } };

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

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?

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

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

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

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

how to even get intuition for such a question , it kinda really trippy

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

//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; }

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; }

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

this question is really hard to unterstand pleasse make it new video with long duration with full explanation i cant understand

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

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

Are we not allowed to use recursion in interviews?

Brilliant, just brilliant!! Amazing Explanation

understood bhaiya thank you very much :)

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

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; }

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

class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: cur=head pre=None tail=None cache=[] while cur: for _ in range(k): if not cur: tail=cache[0] cache=[] break cache.append(cur) cur=cur.next nxt=cur while cache: cur=cache.pop() if pre: pre.next=cur else: head=cur pre=cur cur=nxt pre.next=tail return head

Awsm!!😄 Striver Sir aka bhaiya!!

why we are not performing normal reverse technicque ?

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

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

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?

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

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

I think easier way to do this is keep iterating and reverse k group of nodes. Now for last group if (count

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

why do u complicte the explanation so much if it is so simple

bhaiya eagerly waiting for your tree series.

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

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

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

Wonderful explanation !!

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

Very good explanation understood in one hour

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

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)

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

Just Wow!! what an explanation sir

Here, because I was rejected in an interview due to such dumb and unrelated problem.

Understood it in 7th or 8th attempy 😂 💖

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; }

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

kisiko kuch bhi lage yhi sab hindi me padha diya hota to har koi samaj jata actually khud bhi explain nhi kar pa raha hai bhai .

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

Ehh....I done it in simple way without this method and 94% faster too 🤔.....is there any problem

how is dummy->next the head of new linked list?

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

After a long time!