Reverse Nodes in K-Group - Linked List - Leetcode 25

[@NeetCode]

Linked List Playlist: kzbin.info/www/bejne/fWHCemCQe5WGaZo

[@pizzatime9565]

One of those problems you know how to solve but can't. Very frustrating.

[@jegadheeswarank6290]

because of it.... I feel like dumb

[@akshaychavan5511]

You should try recursive solution for this. It is much more intuitive.

[@tomonkysinatree]

I feel like this happens to me quite a bit. Conceptually I understand, but when I got to start writing the code I get confused. Start getting tied up in the details. It's hard for me to even put in words what ties me up.

[@derpy566]

Idk if this will still help after a year, but I'm surprised this question used a much more difficult solution. I did this question right after 92. Reverse Linked List II and the logic flows really smooth. All you have to do is find the size first and then pretend like you are doing Neetcode's solution for 92 for (size//k) times. When your dummy is replacing dummy.next with the reversed LL and dummy.next.next to fully connect the LL. All you have to do is move dummy to right before the next k-group. Do this and all of a sudden you just add like 2 lines to neetcode's solution for 92 for it to work. temp_head, size = head, 0 while(temp_head): temp_head = temp_head.next size += 1 dummy = ListNode(0, head) prevNode, prevNodeTracker, cur = dummy, dummy, head for i in range((size//k)): prev = None for j in range(k): #Moving cur along temp = cur.next #Reversing, using prev as history cur.next = prev prev = cur #Moving cur along cur = temp #Moving Prevnode along k group prevNodeTracker = prevNode.next prevNode.next.next = cur prevNode.next = prev #Moving Prevnode along k group prevNode = prevNodeTracker return dummy.next

[@nammi895]

Okh If by any chance this question is coming to interview I'll tell him I've previously seen this question. If he insist, then I'll say kindly fail me in interview, this question is literally harrasment There are plenty of good companies, better luck with next one.

[@nikhil199029]

welcome to 2024.

[@utkarshagupte1178]

I always hated linked list sums but your explanation has made them so much easier for me. Please keep uploading more solutions.

[@NeetCode]

Thank you, I will! :)

[@leonscander1431]

I did it slightly easier. I created a dummy node that points to nothing and instead of reversing groups in place I moved the reversed groups to the end of that dummy node. So basically it's a separate list (but space is still O(1) because we're just moving links). Also I'm not seeking the end of each group (getKth function in video), I'm just reversing the group as I go through it then append it to the dummy list. But this way we can reverse the last group which can be too short. So I reverse it again (if i < k condition) to turn it to original state. So this solution is O(n) + O(k) in case if there is a last group with size < k and O(n) if all the groups are complete. def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: dummy = ListNode() tail = dummy node = head while node is not None: prev = None group_tail = node i = 0 while node is not None and i < k: next = node.next node.next = prev prev = node node = next i += 1 group_head = prev if i < k: prev = None node = group_head while node is not None: next = node.next node.next = prev prev = node node = next group_head, group_tail = group_tail, group_head tail.next = group_head tail = group_tail return dummy.next

[@TwoShotsOfAdventure]

Thankyou! this is so easy to understand.

[@kathypeng6066]

This is a super complicated linked list problem and I thought I would never understood it. You did a great job convincing me otherwise!

[@vasuarora_]

Haha😂😂

[@mehdihajian5643]

This was extremely confusing. I hope you revisit this solution.

[@alexandrep4913]

It doesn't get better.

[@AsliArtist]

@@alexandrep4913 I think what OP meant was that @neetcode lazied his way out of explaining the pointer manipulation at the end.

[@The6thProgrammer]

I love the Neetcode solution videos but my own approach in this one felt easier to understand. Instead of using a dummy node, I just treated the first k nodes as a special. That is, I reverse the first k nodes so I can initially set a few values to use going forward (e.g. for 1->2->3->4->5, with k =2, I first reverse 1->2 which yields 2->1->nullptr). The values I capture are newHead (which is what I will return at the end of the entire algorithm, this gets set to the last value encountered in the first list which is 2) and then I set a value called prevTail which is the tail of the reverse list from the previous group of k nodes (which is 1 in this case). So prevTail = head, and then newHead = prev once the list is reversed. With that in place it's fairly easy to just keep reversing k nodes in a row and at the end set prevTail->next = prev and prevTail = currHead every time. Then at the end just make sure to set prevTail->next = curr. If the length of the linked list is a multiple of k, curr will be null, otherwise curr will point to the head of the remaining unreversed portion of the list. You could advance k everytime to see if k nodes exist, but I just iterated through the entire list up front and counted the total nodes, and then divided by k to determine how many iterations I needed to perform before terminating. Here is a link to the solution: leetcode.com/problems/reverse-nodes-in-k-group/solutions/4090426/c-determine-total-node-count-reverse-first-k-nodes-and-then-iterate/

[@tomato2699]

i made minor editions to the code because to make it more braindead for myself. The main difference is that I used prev_node = None instead of skipping the steps and doing prev_node = node_after_sublist. At every iteration for each sublist we just need to keep track of the node_before_sublist, node_after_sublist, initial_starting_node and initial_kth_node. With those 4 pointers, we can safely reverse the sublist, following which, we can just ensure that the nodes before and after the sublists are being linked to the correct nodes, before updating the new node_before_sublist and moving to a new iteration. class Solution(object): def reverseKGroup(self, head, k): """ :type head: ListNode :type k: int :rtype: ListNode """ prehead = ListNode(0, head) node_before_sublist = prehead while True: initial_starting_node = node_before_sublist.next initial_kth_node = self.get_kth_node(node_before_sublist, k) if initial_kth_node == None: break node_after_sublist = initial_kth_node.next prev_node = None current_node = node_before_sublist.next while current_node != node_after_sublist: next_node = current_node.next current_node.next = prev_node prev_node = current_node current_node = next_node node_before_sublist.next = initial_kth_node initial_starting_node.next = node_after_sublist node_before_sublist = initial_starting_node return prehead.next def get_kth_node(self, prev_node, k): current_node = prev_node while current_node and k > 0: current_node = current_node.next k -= 1 return current_node

[@NeptuneTales]

Thank you, setting prev_node to None in the process really helps understanding the solution.

[@barked2786]

thankyou very much bro, i understand now

[@Asdelatech]

Bro thank you so much! that's perfect!

[@durgeshsrinivasyathirajam44]

Your videos are amazing!!! I just saw the first 10 videos for Linked list and I was able to understand the solutions clearly!!

[@NeetCode]

That's awesome, I'm happy they were helpful!

[@gladyouseen8160]

@@NeetCode hey please provide the spreadsheet that shows the order of videos to learn in your KZbin channel

[@nchou646]

Really like the way u explain all these leetcode question, I hope the company u working for has very good wlb, so you may have time to upload more videos lol

[@rajeshkr12]

Yes goog will give him ample time I hope lol !!

[@venkatasundararaman]

We can call reverseKGroup recursively and I felt that was much more easier to understand. We can reverse the first k elements and after reversing we can point the last one to the recursive call for reverseKGroups

[@tusharsaxena8239]

but that's not O(1) space

[@RobWynn]

@@tusharsaxena8239 how is it not O(1) space?

[@jcastro5130]

@@RobWynn call stack

[@RobWynn]

@@jcastro5130 thanks dawg

[@mr6462]

This is a very hard problem. Thanks for your explanation.

[@fuzzywuzzy318]

this question only increase my depression because it made me feel myself like a numb

[@ax5344]

prev = kth.next confuses me, 1-->2 --> 3 -->4, k=2; kth.next =3, why would we want to set prev = 3?

[@wolemercy]

Because at the end of the reversal, you want 1 to be pointing to 3 To illustrate, setting prev to 3 essentially has this effect at the start of the reversal: 3 -> 1 -> 2 || So when the reversal is complete, you are left with; 3 3 -> 4

[@ThePacemaker45]

@@wolemercy thanks a lot, was really confused by that till I saw this.

[@matthewsaucedo2471]

@@wolemercy Excellent explanation, thank you so much! Great community here.

[@cannguyen9044]

@@wolemercy But actually In the first reverse we handle for 1 -> 3 ? why we need to re-assign ? Could you explain for me ?

[@randomBoulevards]

Even more understandable solution (bit tricky): class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if not head: return head start, prev, tail, curr = head, head, head, k while curr and tail: prev = tail tail = tail.next curr -= 1 if not tail: if curr: return head prev.next = None res = self.reverseLL(start) start.next = self.reverseKGroup(tail, k) return res def reverseLL(self, head): # code to reverse LL prev, tail = None, head while tail: temp = tail.next tail.next = prev prev, tail = tail, temp return prev

[@danielshvartz9702]

This is why i'm fearing linkedlist problems. like, i know how to solve this, but i have to remember 100 pointers and move them, and to draw out this it will take my whole time on an interview.

[@Asdelatech]

Thank you so much, man! You literally saved me from a lot of stress!

[@digestable_bits]

this solution tops all others and is easiest to follow, you the man! :)

[@shrunkensimon]

Could you elaborate or point to what the potential edge cases might be if we didn't use a dummy node? Appreciate your work, thank you.

[@itachid]

Took me a while to understand the part from 10:40. But I got it after a bit of brainstorming. It really helps if you write down the LL on a piece of paper.

[@videowatcher4852]

Could you explain that part pleaseee

[@johnchen0213]

JESUS! THIS IS SO HARD! I STILL DON"T GET IT

[@symbol767]

Agreed, its a terrible question overall too.

[@SergeyAngelov]

This one seems more medium than hard. The only challenging part is how to not reverse if number of elements is less than k. I've simply added another reverse loop for last group in this case, so elements are put back in order.

[@leonscander1431]

same

[@m_jdm357]

This problem is really good and makes a lot of sense.

[@nekoconer9036]

can say this video will be my best salvation

[@shklbor]

such clarity of thought, excellente solution!!

[@ДенисГарбуз-ф9ш]

my solution looks little spaghetti in compartion, but uses little different approach what is interesting compare to, basically both , video approach and mine works in O(2n) which O(n). In this case pivot - groupPrev. I initially iterate all nodes to count total length and know amount of groups based on that. def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if k == 1: return head dummy = ListNode(0, head) length = 0 curr = head while curr: length += 1 curr = curr.next length //= k prev, curr = None, head pivot = dummy for i in range(1, (length * k)+1): nxt = curr.next curr.next = prev prev = curr curr = nxt if i%k == 0: pivot.next.next = curr temp = pivot.next pivot.next = prev pivot = temp prev = None return dummy.next

[@akshaychavan5511]

Recursive solution - class Solution: # returns first node and last node of the revered list def reverse(self, head): if head == None: return None prev = None current = head while current: nxt = current.next current.next = prev prev = current current = nxt return (prev, head) def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if not head: return head kBackup = k newHead = head start = head while head: if k==1: # kth node found newHead = head nextListStart = head.next head.next = None # break the link first, last = self.reverse(start) last.next = self.reverseKGroup(nextListStart, kBackup) # recursively call for remaining list k-=1 head = head.next return newHead

[@anilprasad5120]

They asked me this question in Qualcomm. Got rejected.

[@yi-ruding]

Hi, just found the Python solution in Neetcode is wrong...You may want to replace it with the correct one :)

[@your_name96]

I understood after drawing and running some cases by hand

[@ajajajaj686]

A recursive solution is more intuitive but of course, is not O(1) in terms of extra space.

[@kakhatezelashvili3368]

groupPrev.next = kth is confuses me :) Is not kth the first node after reversal ?

[@your_name96]

before the first iteration, the groupPrev was the dummy node , it's next value is 1 right, even after the first iteration the groupPrev.next is 1 and the kth is 2, hence we need to do 2 things , 1. point groupPrev.next to 2 and then update the groupPrev to 1 (the last node), so for doing 1 we need to save the last node aka groupPrev.next value(1) and then point to 2.

[@Alisa-ym7rr]

@@your_name96 Hi I am confusing why we need to make groupPrev.next to 2, and how can groupPrev be 1 and groupPrev.next is 2? isn't 1'next point is 3? Thanks...I am so confusing this part

[@taroserigano6546]

@@Alisa-ym7rr you have to separate groupPrev and the actual nodes. [1] still points to [3] -> [4], this will not be affected by groupNext.next = [2]. groupPrev.next = 2 is only simply to connect dummy[0] -> [2] and then placing the groupPrev to [1], which still points to [3]

[@videowatcher4852]

@@taroserigano6546 I think I finally understood it after hours because of this comment :) thanks!!!

[@singletmat5172]

Ty for the consistent uploads!

[@aynuayex]

here is without using helper function dummy = ListNode(0, head) groupPre = dummy while True: count, kth = k, groupPre while kth and count > 0: kth = kth.next count -= 1 if not kth: break groupNext = kth.next pre, cur = groupNext, groupPre.next while cur != groupNext: tmp = cur.next cur.next = pre pre, cur = cur, tmp tmp = groupPre.next groupPre.next = kth groupPre = tmp return dummy.next

[@subham621]

Can you please let me know if the following statement is correct regarding the Time and Space complexity for this solution? Since we are counting k nodes each time and reversing the k nodes again. It's like traversing through the same node twice. I think the Time complexity should be O(n). Space complexity should be O(n/k). Since we are calling the recursive function n/k times and that would take up some space within the call stack.

[@1pomii]

the getkth node is not recursive

[@SaqibMubarak]

Great Explanation

[@dawidkorzepa3665]

It’s easier, but you have to use extra memory, which violates the constraints.

[@cathyhuang8557]

You are so helpful~

[@crayonbandit7]

I did not quite get the shifting of groupPrev towards the end of the first while loop. Could someone please help me?

[@ishwaripednekar5164]

I have found couple of videos for this, but this is at next leve;

[@heathled]

really good explaination

[@raunaqsingh875]

Very good explanation

[@adbuth4854]

solutions are just awesome

[@qR7pK9sJ2t]

Simply magical !!!

[@symbol767]

I hate these useless questions... we're not even gonna be using this nonsense on the job

[@Sulerhy]

Linked List problems are easy to have idea of solution. But coding it is so frustrating

[@hoyinli7462]

ur great teacher!

[@samarthkaran2314]

I understood the whole just having problem with these 3 lines Tmp=groupPrev.next groupPrev.next=kth groupPrev=tmp I know we have to update groupPrev to point to the last pointer of the group so that next group k is calculated perf But updating its next to kth which is 2 after first iteration is where i need help to understand.. am i miss interpreting something ? Because in the 2nd iteration curr with be kth i.e groupPrev.next

[@carloscarrillo201]

It's just connecting the 2 lists back (groupPrev and groupNext)

[@your_name96]

before the first iteration, the groupPrev was the dummy node , it's next value is 1 right, even after the first iteration the groupPrev.next is 1 and the kth is 2, hence we need to do 2 things , 1. point groupPrev.next to 2 and then update the groupPrev to 1 (the last node), so for doing 1 we need to save the last node aka groupPrev.next value(1) and then point to 2.

[@todorads]

In 2nd iteration it will connect last element from previous group (groupPrev) to first element from next group (kth after reversal). Basically it connects groups. In first iteration it did the same but with dummy node instead of group

[@yohguy4655]

Good explanation.

[@NeetCode]

Thanks!

[@rishabhbhatt7373]

can someone explain the time complexity ? Is it O(Nk)

[@minciNashu]

i've found out that drawing this stuff on paper makes me understand better what's going on with these pointers

[@sase1017]

but your solution is diff from the picture

[@vallabhchugh2075]

i wish you did a dry run with code

[@staywithmeforever]

I solved it with 200ms Optimal will be around 30-40😅

[@nirajan7463]

Just new to programming how is this solution a = [1, 2, 3, 4, 5] n= [] k = 2 c = 0 for i in range(len(a)): n.insert(c, a[i]) if (i+1)%k == 0: c = (c+ 1)*k print(n)

[@internick_]

Nah this one is hell

[@batnasn]

alarm sound on the background, wtf happened

[@eminmammadov6525]

God, this is confusing

[@ameynaik1755]

No way this is easy for me X(

[@IK-xk7ex]

hello, thank you for video, but you've used the stack data structure. As I see it takes memory space O(k). So it doesn't totally fit the problem requirements. Anyway it's easy to replace replace recursion by the loop, so for someone it will be a homework :)

[@Krokrodyl]

There is no stack and no recursion in this video.

[@adityan5302]

Python Solution using recursion VERY EASY: def findLength(self, curr): l = 0 while curr: l += 1 curr = curr.next return l def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if head==None or head.next==None or k==1: return head l = self.findLength(head) def helper(head, l, k): if l < k: return head if l >= k: count = 0 temp = head prev = next = None while count < k: next = temp.next temp.next = prev prev = temp temp = next count += 1 l = l - k head.next = helper(temp, l, k) return prev return helper(head, l, k)

[@pipicacadanslepot]

recursion would make it not O(1) space tho

[@ashkan.arabim]

so many damn variables :/

[@vipulsharma1897]

Not the best of your work, honestly.

[@ericsodt]

You're a terrible explainer. I'm not sure how you got so popular with this stuff...

[@jeremygong4190]

im a little confused, but isnt that just set a slow pointer and a faste ptr k steps ahead, and whenever the first encounter switch slow to be at k->next, and then repeat this step...?