@@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).
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.
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
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
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.
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; } };
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).
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;
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...
@@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;
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
@@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.
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
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.
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; }
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
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
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
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
@@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
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); } };
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?
@@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.
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
@@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
@@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
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; }
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!
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
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
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?
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 .
@@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
@@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 👍
@@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
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
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
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; }
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
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.
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 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.