Reverse Nodes in K-Group - Linked List - Leetcode 25
Вставка
- Опубліковано 25 чер 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: leetcode.com/problems/reverse...
0:00 - Read the problem
2:10 - Drawing solution
6:45 - Coding solution
leetcode 25
This question was identified as a Microsoft interview question from here: github.com/xizhengszhang/Leet...
#linkedlist #microsoft #python - Наука та технологія
Linked List Playlist: ua-cam.com/video/G0_I-ZF0S38/v-deo.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.
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.
This was extremely confusing. I hope you revisit this solution.
It doesn't get better.
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!
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 UA-cam channel
this solution tops all others and is easiest to follow, you the man! :)
Ty for the consistent uploads!
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 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
This is a very hard problem. Thanks for your explanation.
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 problem is really good and makes a lot of sense.
such clarity of thought, excellente solution!!
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 understood after drawing and running some cases by hand
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
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.
can say this video will be my best salvation
solutions are just awesome
ur great teacher!
Very good explanation
A recursive solution is more intuitive but of course, is not O(1) in terms of extra space.
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
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?
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 ?
Simply magical !!!
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
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
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 have found couple of videos for this, but this is at next leve;
this question only increase my depression because it made me feel myself like a numb
Good explanation.
Thanks!
Hi, just found the Python solution in Neetcode is wrong...You may want to replace it with the correct one :)
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've found out that drawing this stuff on paper makes me understand better what's going on with these pointers
Great Explanation
It’s easier, but you have to use extra memory, which violates the constraints.
can someone explain the time complexity ? Is it O(Nk)
JESUS! THIS IS SO HARD! I STILL DON"T GET IT
Agreed, its a terrible question overall too.
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!!!
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
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 wish you did a dry run with code
I solved it with 200ms
Optimal will be around 30-40😅
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.
No way this is easy for me X(
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
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
God, this is confusing
I hate these useless questions... we're not even gonna be using this nonsense on the job
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...?