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

Linked List Playlist: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-G0_I-ZF0S38.html

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

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.

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

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.

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

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

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

Ty for the consistent uploads!

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

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/

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

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

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

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

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

You are so helpful~

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.

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

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

such clarity of thought, excellente solution!!

ur great teacher!

solutions are just awesome

can say this video will be my best salvation

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

I understood after drawing and running some cases by hand

Simply magical !!!

Very good explanation

really good explaination

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

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

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.

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.

Good explanation.

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

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

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

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

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

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.

They asked me this question in Qualcomm. Got rejected.

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

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

Great Explanation

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

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

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

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

i wish you did a dry run with code

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

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

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

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)

No way this is easy for me X(

alarm sound on the background, wtf happened

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

God, this is confusing

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

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)

so many damn variables :/

Not the best of your work, honestly.

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