@@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.
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
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; } };
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; } }
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
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.
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;
@@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.
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
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
#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 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; }
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;
@@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
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;
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!
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
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; } };
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.
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
@@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
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
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.
@@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
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 👍
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
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++;
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.
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
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; }
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?
@@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
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
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.
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
Doing 1-1 interactions on every Sunday or Monday on Instagram Live, do join :) Insta: instagram.com/striver_79/
@@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
I think we have to assign dummy->next to kth Node.
@@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.
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
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;
}
};
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;
}
}
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.
thanks for this i was confused about this
Thanks man !
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
acc to ur concept, he has made curr and nex also point to dummy , then why only pre is effecting it???????
samajh nai aa rha ......can explain plzzzzzzz????????
how pre is changing the node to which dummy points.
To break it down at 8:36 was super cool. Btw appreciate your hard work sir:)
accent lol
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 ?
Awesome explanation. Was stuck with this problem for more than 3 hours. Very clear and crisp explanation. Saved my day. Thanks.
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.
After watching it 3times , I understand😉
+1 😂😂
I thought I am the only one 😢
my record 4 times
My record 3 days
@@aesthetic_vibes_404 guess I'm gonna break it ☠️
I was asked this question in an interview and I fumbled a lot because I tried recursion. This solution is way simpler and easy.
which company
@@preetkatiyar969 it was for a startup called thinkify labs
Recursion was way easier
@@LEO-ds7pe would not you need O(N) space for recursion with O(N) time ?
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;
Thankyou for a different approach! Interviewbit provided a recursive approach for this question which ig isnot good!
Again thanks!
Glad you enjoyed it!
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...
@@rohitgpt7201 Okay thankyou for the information
@@rohitgpt7201 exactly!
@@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;
8:35 so you just break it thown... That was cool
also "last node" @16:48 😂😂
@@deepaliraghuvanshi9775 exactly whats with that accent?? ;))
I was also going to comment the same
5:59 "so whot we gonna follow".
@@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
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
Super happy I solved in 1st attempt without solution. Thanks.
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
Just great bro. I tried everytime this problem but the way u explained, thanks a lot bro.
Glad it helped
Getting better and better every day!
explaining this method to interviewer is a task itself
I always thought linked list is scoring , but after solving this one, i am
Great video....I understood it after watching the video twice and dry running the code by myself ❤
#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
wow,i sloved it by myself, feeling proud
This is converted to leetcode easy after your explanation..
I must say you are a genius.. Because I am still feeling it really tough
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;
}
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)
Thanks! By drawing it on paper, I understood it quickly!
I bet no one can remember the process after 2-3 days of learning it.
I spend my 6 hr to solve this question and Pass a few test cases. yes its the toughest problem of linked list.
Simple jo reverse a ll ka code hai vahi hai bs add a condition of count
Awsm!!😄 Striver Sir aka bhaiya!!
Just tell us why you wrote
next->next = pre->next ...........instead of "cur" ......
You supposed to tell but you forgot.
On 8:28, curr is a different node and pre's next is the node, where we have to connect the nex's next.
thank you bhai, for this one 😍, mazaaaaa aagaya🔥
GOD BLESS YOU!!!
I think the recursive approach is easy to understand, But you did it well !!
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 in every recursive call , calculate length of LL. If k>length just return the list, else next recursive call.
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
Great explanation Buddy. Learning new and efficient approach every day. Thanks for everything @striver 🔥.
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 u can use same reversing logic...just the number of reversing ptrs will be less than k-1 .....it will be n%k ....
Sir, is it important to consider the dummy node?
Brilliant, just brilliant!! Amazing Explanation
I found the recursive way to reverse this very intuitive compared to the iterative one
sir can you explain that how come dummy next point to the new modified list?
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;
}
👍👍👍
Where did we point dummy->next to node 3 ???
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;
}
your solun is consuming O(n) space recursively.
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!
Thanks Really Great Explanation!! Drawing on paper was easy to understand
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
Thank u so much guruji , great explaination 💗💗
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;
}
};
understood bhaiya thank you very much :)
Just Wow!! what an explanation sir
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.
Count should be initialized with 1 for counting the the length of LinkedlList
We start with dummy node if you carefully observe, so it works!!
@@takeUforward yup, got it.
8:35 break it down, comes with an accent😂
Very good explanation understood in one hour
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.
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
I think easier way to do this is keep iterating and reverse k group of nodes. Now for last group if (count
your code is bulky... just one modification is enough
check here..
struct node *reverse (struct node *head, int k)
{
if(head==NULL || k==1) return head;
node* dummy = new node(0);
dummy->next = head;
node* curr = dummy , *prev=dummy,*nxt=dummy;
int count = 0;
while(curr->next){
curr=curr->next;
count++;
}
while(count>1){ //change 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;
}
C++ code is wrong because when I try to implement it in leetcode output is same as input.
Converting the list into Cylic linked list was nice...
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
I think one change required when you are calculating length of instead of cur->next!=NULL it should be cur!=NULL
Given code works fine.. has been tested and then explained..
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.
@@gautamsuthar4143 yea yes right and thanks for clearing ✌️
@@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
I kept the same condition as striver did ,just initialize/start the with count =1 ;
understood, thanks for the great explanation
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
Which one to tell in interview, this or the recursive one
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?
Plz show your approach's code.
I have also tried this approach but im not getting correct answer can you show your code
@@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.
@@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;
}
Are we not allowed to use recursion in interviews?
if k = 3 and there are two nodes remaining at last, what should i do to rotate those 2 nodes as well
@@SanjaySingh-xw3mi she asks if we have to !
@@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
did u find ?
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?
Yes you are right because of that it showing output same as input
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 👍
@@adarshdubey1784 i didnt get it , can you please make the changes in strivers code ? i would be grateful
Bro ur way of explaining is awesome. Thanks a lot
Hey please could someone tell me why pre->next instead of cur
Wonderful explanation !!
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
pre is dummy node or dummy pointer i mean pre->next will be different in these two cases...kind of confused.😕
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
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);
}
};
//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;
}
not getting the part where you return dummy->next as new head.... as initially you assign dummy->head, so how dummy->next update
Thanks, bro, your explanation is always helpful.!!!!!1
How is the address in dummy pointer changing??? We are not changing its value so it should always point to 1 only?
did u find the answer ? i have same doubt
i've seen this in an amazon interview..kind of hard to get it on the whiteboard.
So, were u able to solve it completely or partially ?
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.
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
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)
why we are not performing normal reverse technicque ?
Understood it in 7th or 8th attempy 😂 💖
bhaiya eagerly waiting for your tree series.
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;
}
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;
}
Great Job brother❤💙✨
@8:35 :}. Bhaiya ki accent.
Can't we just swap the value of first node and last , like this and last would be null for later section
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?
What is the intution behind the approach , i mean reccursive solution has an intution but this solution is hard to get
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
Find a reason to live/work. For more information watch the movie, "The Shawshank Redemption"
can anyone please explain last line of the code, how come dummy->next has the head of updated list
For the First group reversing can we do without creating dummy ?
correct me if I am wrong ?
we can.. But handling the edge cases would be a tedious job without the dummynode
Reversing k nodes and then recursively call for next won't be a good solution?
Recursive stack will increase space complexity
@@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
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
8:35 break it downnnnnnnnnn
Bhaiya agr is q m each k groups ko reverse krke arrange kre to tb bhi n m hoga
What an explanation!!!!!!!!!!!!!
4:40 - 8:00
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.
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
Do a dry run once to get stuffs cleared..