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.
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
@@derpy566 DERPY! You ARE THE MAN! I have been working on this problem for 2 days now, refusing to give up. You absolutely nailed it. PLEASE @neetcode, PIN DERPY'S COMMENT - it saved me time 🥲🥹
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.
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/
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
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 """
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
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
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
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.
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
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.
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.
@@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
@@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]
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.
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
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.
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
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
I think you should redo this walkthrough, the solution is good but describing the groupNext and groupPrev ideas during the walkthrough would make it much easier to understand the solution in code, instead of leading with "assigning to NULL for now"
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
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.
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
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)
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)
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 :)
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...?
Linked List Playlist: th-cam.com/video/G0_I-ZF0S38/w-d-xo.html
One of those problems you know how to solve but can't. Very frustrating.
because of it.... I feel like dumb
You should try recursive solution for this. It is much more intuitive.
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.
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
@@derpy566 DERPY! You ARE THE MAN! I have been working on this problem for 2 days now, refusing to give up. You absolutely nailed it. PLEASE @neetcode, PIN DERPY'S COMMENT - it saved me time 🥲🥹
I always hated linked list sums but your explanation has made them so much easier for me. Please keep uploading more solutions.
Thank you, I will! :)
This is a super complicated linked list problem and I thought I would never understood it. You did a great job convincing me otherwise!
Haha😂😂
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.
welcome to 2024.
@@nikhil199029 yeah this is a standard question in 2024 lol
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!!
That's awesome, I'm happy they were helpful!
@@NeetCode hey please provide the spreadsheet that shows the order of videos to learn in your TH-cam channel
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
Thankyou! this is so easy to understand.
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
Thank you, setting prev_node to None in the process really helps understanding the solution.
thankyou very much bro, i understand now
Bro thank you so much! that's perfect!
This was extremely confusing. I hope you revisit this solution.
It doesn't get better.
@@alexandrep4913 I think what OP meant was that @neetcode lazied his way out of explaining the pointer manipulation at the end.
Agreed. I don't understand the pointer manipulation at the end at all
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
Yes goog will give him ample time I hope lol !!
This is a very hard problem. Thanks for your explanation.
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
but that's not O(1) space
@@tusharsaxena8239 how is it not O(1) space?
@@RobWynn call stack
@@jcastro5130 thanks dawg
I put the nodes into a vector and got an accepted solution and I am not ashamed to say it!
this solution tops all others and is easiest to follow, you the man! :)
prev = kth.next confuses me, 1-->2 --> 3 -->4, k=2; kth.next =3, why would we want to set prev = 3?
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
@@wolemercy thanks a lot, was really confused by that till I saw this.
@@wolemercy Excellent explanation, thank you so much! Great community here.
@@wolemercy But actually In the first reverse we handle for 1 -> 3 ? why we need to re-assign ? Could you explain for me ?
this question only increase my depression because it made me feel myself like a numb
can say this video will be my best salvation
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.
Could you explain that part pleaseee
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
This problem is really good and makes a lot of sense.
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.
Thank you so much, man! You literally saved me from a lot of stress!
such clarity of thought, excellente solution!!
Ty for the consistent uploads!
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.
using sub function here a bit
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
group_prev = dummy
def getkth(curr, k):
while curr and k > 0:
curr = curr.next
k -= 1
return curr
while True:
kth = getkth(group_prev,k)
if not kth: break
group_next = kth.next
# reverse group
prev = kth.next
curr = group_prev.next
while curr != group_next:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
tmp = group_prev.next
group_prev.next = kth
group_prev = tmp
return dummy.next
groupPrev.next = kth is confuses me :) Is not kth the first node after reversal ?
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.
@@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
@@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]
@@taroserigano6546 I think I finally understood it after hours because of this comment :) thanks!!!
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.
the getkth node is not recursive
I understood after drawing and running some cases by hand
A recursive solution is more intuitive but of course, is not O(1) in terms of extra space.
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
They asked me this question in Qualcomm. Got rejected.
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.
same
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
Hi, just found the Python solution in Neetcode is wrong...You may want to replace it with the correct one :)
You are so helpful~
really good explaination
Very good explanation
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
solutions are just awesome
I have found couple of videos for this, but this is at next leve;
I did not quite get the shifting of groupPrev towards the end of the first while loop. Could someone please help me?
Simply magical !!!
I think you should redo this walkthrough, the solution is good but describing the groupNext and groupPrev ideas during the walkthrough would make it much easier to understand the solution in code, instead of leading with "assigning to NULL for now"
JESUS! THIS IS SO HARD! I STILL DON"T GET IT
Agreed, its a terrible question overall too.
ur great teacher!
Linked List problems are easy to have idea of solution. But coding it is so frustrating
Great Explanation
It’s easier, but you have to use extra memory, which violates the constraints.
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
It's just connecting the 2 lists back (groupPrev and groupNext)
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.
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
can someone explain the time complexity ? Is it O(Nk)
i've found out that drawing this stuff on paper makes me understand better what's going on with these pointers
Good explanation.
Thanks!
i was asked this question for an intern position
quite complex code!
I solved it with 200ms
Optimal will be around 30-40😅
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)
recursion would make it not O(1) space tho
i wish you did a dry run with code
No way this is easy for me X(
but your solution is diff from the picture
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)
alarm sound on the background, wtf happened
God, this is confusing
I hate these useless questions... we're not even gonna be using this nonsense on the job
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 :)
There is no stack and no recursion in this video.
Nah this one is hell
so many damn variables :/
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...?
Not the best of your work, honestly.
You're a terrible explainer. I'm not sure how you got so popular with this stuff...