I hate linked list problems. They all reduce to fairly simple ideas made utterly incomprehensible by trying to keep track of sixteen pointers, some significant portion of which are temporary. Just a garbage data structure.
Although I understand your frustration, LLs are used as a primary data structure in most of the embedded systems. So its good to have knowledge of this!
The key to understand this problem is to identify it’s a merging problem, basically the desired sorting can be achieved by splitting the linked list into 2 halves, reverse the second half then merge it in the first half. Wouldn't want to be asked this in an interview tbh :D
I did this question in a complete different way using an array and two pointers. I think my solution was cheating somehow but I don't really know: def reorderList(self, head: Optional[ListNode]) -> None: listStack: list[ListNode] = [] nh = head while nh: listStack.append(nh) nh = nh.next l, r = 0, len(listStack) - 1 while l < r: listStack[l].next = listStack[r] listStack[r].next = listStack[l+1] l += 1 r -= 1 if len(listStack) % 2: listStack[r].next = None else: listStack[r+1].next = None
@@luizferreira3986 yeah the space complexity suffers, but still a good solution. always good to have new ways to do things, even if its not the most efficient, opens up your way of thinking.
Makes you feel like a node yourself huh? . . . . . Joke was that NeetCode likes having dummy nodes in his linkedlist problems dummy = ListNode() Sorry, ik it was a bad joke 😭
This is a great explanation. Linked list questions are generally hard for me to grasp but this vid really explains it so well and straightforward. Thank you so much!
heres my slightly different solution class Solution: def reorderList(self, head: Optional[ListNode]) -> None: #find middle slow = head fast = head while fast.next and fast.next.next: fast = fast.next.next slow = slow.next #need node before second half to split list second = slow.next slow.next = None prev = None while second: temp = second.next second.next = prev prev = second second = temp temphead = head while prev: #shorter if odd temp1 = temphead.next temp2 = prev.next temphead.next = prev prev.next = temp1 temphead = temp1 prev = temp2
Thanks! really helpful.. Great videos! One suggestion - Placing/explaining your drawings alongside the code would make it even easier to understand, else its usually pain going back and then again coming back to the code!
Sometime s and f pointers points to head initially. Sometime they refers to head and head.next. Is there any marker to choose appropriate values to initialise with?
Starting slow and fast both at head works fine as well. No need to `slow, fast = head, head.next` as then you'll need to `second = slow.next` to make up for the lead fast has.
conceptually this problem was easy for me. Keeping the pointers straight and where I was at in the lists at each part in the code was the problem for me.
Initially I used a deque and simply popped from front and back. Of course this has O(n) space complexity, so your solution is better :) Thanks for explaining
I used a dictionary to traverse and store the linked list nodes with index location. Then I used left and right pointers to traverse the index and reorderd by pulling the related nodes from the dictionary. It was intuitive to me and one of my first problems I could solve on my own before watching the video
i think i am having the hang of it. i mean i understand the question come up with a way to do it, after remembering palindrome problem, clear and concise: # find middle slow, fast = head, head while fast and fast.next: slow, fast = slow.next, fast.next.next
# reverse second half(right) pre, cur = None, slow while cur: temp = cur.next cur.next = pre pre = cur cur = temp # reorder list cur = head while cur != pre and pre: temp_l, temp_r = cur.next, pre.next cur.next = pre pre.next = temp_l if pre.next else None cur = temp_l pre = temp_r
my first approach was the array based which i know is not inplace, but seeing this approach really feels good especially the fast and the slow pointer one .. great
why the initial value of fast is head.next instead of head like the slow pointer? then you don't need to manually adjust slow pointer to slow.next outside of the while loop
My idea was to find the midpoint, remove from list and append to a stack, and keep doing this until we're down to the first element of the linked list. Then pop from stack and point cur to the popped node until stack is empty (intuition is that the mid point becomes the last node as we remove an element). It passed 9/12 test causes but timed out unfortunately since it's N^2. stack = [] cur = head while cur.next: fast, slow = head, head slowPrev = head while fast and fast.next: fast = fast.next.next slowPrev = slow slow = slow.next slowPrev.next = slow.next q.append(slow) while stack: node = stack.pop() cur.next = node cur = cur.next cur.next = None
You could make it O(n) time and O(n) in space. If you just pushed the nodes after midpoint into stack. Then you can pop them back starting from head. (essentially pushing and popping into stack will reverse the later half, and then we just merge them with head to midpoint).
How did you know that the fast/slow pointer would get you to the center of the list? 5:48 Is this just something you have memorized? Is there some practice I could do to more easily be able to intuit this algorithm?
i dont know why but it happend to me a couple of times when i struggle with a problem i just open your video and hear hello everyone lets write some more neetcode. the idea of the solution pupup fast :))))
Kind of confused...what is ultimately being returned if we dont have to do it ourself? If you return 'first' it now points to null. To make it explicit, i used the dummy node instead and returned it. dummy = head //find middle, //reverse //merge return dummy
hm, I think using a stack here makes the most sense imo. That way we have an easier way of tracking what we visited, though you need to create a wrapper. ``` type element struct { idx int node *ListNode } func reorderList(head *ListNode) { mid := findMiddle(head) midHead := reverseLinkedList(mid) l := head r := midHead for l.Next != nil && r.Next != nil { lTmp := l.Next rTmp := r.Next l.Next = r r.Next = lTmp l = lTmp r = rTmp } } func reverseLinkedList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } h := reverseLinkedList(head.Next) head.Next.Next = head head.Next = nil return h } func findMiddle(head *ListNode) *ListNode { slow := head fast := head for { if fast == nil || fast.Next == nil { return slow } fast = fast.Next.Next slow = slow.Next } } ```
for those who are wondering why we starts the code with head, head.next, cos we need to get to end of the first half, point it to none, we also need access to second half, so this way it make things easier for us.
my first attempt for this problem was a rather bruteforce lol repeat following until head.next.next is not None: head -> (reverse the rest of list) so if we have 1-2-3-4-5 1 -> (5-4-3-2) 1 -> 5 -> (2-3-4) 1 -> 5 -> 2 -> (4-3) 1 -> 5 -> 2 -> 3 -> (4) but this was too slow :(
Hi , here are two excerpts from two of your solutions for finding the middle element. two different implementations, please can you explain the difference: #1.Reorder linkedList #find middle slow, fast = head, head.next while fast and fast.next slow=slow.next fast = fast.next
#2. isPalidrome linkedList #find middle(slow) slow, fast = head, head while fast and fast.next: fast = fast.next.next slow = slow.next
E.g. Linked list head [4,3,2,1]: At the end of #2, slow points to [2,1] At the end of #1, slow points to [3,2,1] This allows him to modify head to be [4,3] by setting slow.next to None. It's just a traversal so modifying slow will modify the original head. In #1 the goal is to get 2 linked lists from splitting the original
@@jamessl1544 slow,fast=head,head while fast and fast.next: fast=fast.next.next slow=slow.next prev=None while slow: temp=slow.next slow.next=prev prev=slow slow=temp first,second=head,prev while second: temp1,temp2=first.next,second.next first.next=second second.next=temp1 first=temp1 second=temp2 this solution doesnt seem to work. anyone has any idea why?
@@yz-me4tq # head [4,3,2,1] slow,fast = head,head.next while fast and fast.next: fast = fast.next.next slow = slow.next # head [4,3,2,1] slow [3,2,1] second = slow.next prev = slow.next = None # head [4,3] second [2,1] while second: tmp=second.next second.next=prev prev=second second=tmp # head [4,3] prev [1,2] reversed second first,second=head,prev while second: tmp1,tmp2=first.next,second.next first.next=second second.next=tmp1 first,second=tmp1,tmp2 # head [4,1,3,2]
class Node: def __init__(self, data): self.data = data self.next = None def reverse(head): curr=head prev=None while curr is not None: temp=curr.next curr.next=prev prev=curr curr=temp return prev def rearrangeList(head): temp=head while temp: temp.next=reverse(temp.next) temp=temp.next return head
Ugh. I understand finding the midpoint and reversing the second half, but merging the two does not make sense to me at all. I dont understand how the pointers are passed around and how it manipulates the head. Ive tried for days just reading through this over and over amd nothing has clicked yet.
NeetCode, could you experiment with having your drawing solution in sync while coding. Assimilation would be faster and we will know why you applied a certain logic
I did this question in a complete different way using an array and two pointers. I think my solution was cheating somehow but I don't really know: def reorderList(self, head: Optional[ListNode]) -> None: listStack: list[ListNode] = [] nh = head while nh: listStack.append(nh) nh = nh.next l, r = 0, len(listStack) - 1 while l < r: listStack[l].next = listStack[r] listStack[r].next = listStack[l+1] l += 1 r -= 1 if len(listStack) % 2: listStack[r].next = None else: listStack[r+1].next = None
If it helps you to better visualize this problem, instead of fast and slow pointer you can just count all the elements first, than iterate until the size/2 or size/2+1 th element (depends if the size is even or odd).
I dont understand how input in form of "List" is taken as argument and made it behave like a Linkedlist. I think input list "head" needs to be converted first to Linkdlist first and then taken as argument. Can someone help me explain how thing work ?
I see your confusion as the input examples may suggest that a Python list of those numbers is being passed to the function. This list is not what is really passed into the function, it simply a visualization of the values in the linked list. Head is really the first node in the linked list.
Not sure if anyone else also created a generic reverse list helper, included mid in the second half and got infinite loops. My understanding is that if we do so, there is no way of removing the connection between the first half and the reversed second half(without adding another iteration)
Why do we need line 14 + 15? (second = slow.next) and (slow.next = None)? Is it because we have to return in place, so the original list can't be altered?
The original list is being altered (the nodes themselves are being changed to point to different nodes). By setting second = slow.next we are storing the head of the second list. Once we have stored the head of the second list safely, we are setting slow.next = None since slow is the last node in our first list, it should be pointing to None. So for a list such as 1 -> 2 -> 3 -> 4 -> 5 -> nullptr, the new result after these 2 operations is 1 -> 2 -> 3 -> nullptr for the first list and 4 -> 5 -> nullptr for the second.
I think either way works, but syntax is a little different. If you use fast=head, you won't need to set "second = slow.next", instead second will just be slow. You can draw it out and it will be more clear! (Anyone please correct me if I'm wrong)
the last node of first part of the linked list becomes the last node of the reordered list, so next variable of that node (whose reference is stored in the slow pointer) is initially set to None
I solved it storing only half of the nodes def reorderList(self, head: Optional[ListNode]) -> None: list_len = 0 node = head while node is not None: list_len += 1 node = node.next half: list[ListNode] = [] i = 1 j = list_len//2 - 1 node = head while node is not None: node_next = node.next if i
While most of your videos are usually top notch, I am disappointed in this video. You do not do this algorithm justice by explaining it properly. Your lazily attempt at explaining the algorithm just gets overshadowed because “now here’s the code surely you all can understand it”. We can’t. An animation of the algorithm would’ve been helpful, instead your 5-year-old drawings were presented and we are expected to understand what’s going on.
Oh my goodness. I guess you should be disappointed at yourself. To understand this problem, you simply need to know 1. traversing a linked list 2. Using slow and fast pointers to reach the midpoint of a LL 3. Reversing a LL All these are easy level questions that have already been discussed in this channel. You can't expect someone to explain all basic concepts in each and every problem. And you're expressing your disappointment as if YOU are owed a detailed explanation
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
I hate linked list problems. They all reduce to fairly simple ideas made utterly incomprehensible by trying to keep track of sixteen pointers, some significant portion of which are temporary. Just a garbage data structure.
Same
Linked List is actually kinda cool
Although I understand your frustration, LLs are used as a primary data structure in most of the embedded systems. So its good to have knowledge of this!
felt
The key to understand this problem is to identify it’s a merging problem, basically the desired sorting can be achieved by splitting the linked list into 2 halves, reverse the second half then merge it in the first half.
Wouldn't want to be asked this in an interview tbh :D
@@tl3231 I don't really understand your question.
I did this question in a complete different way using an array and two pointers. I think my solution was cheating somehow but I don't really know:
def reorderList(self, head: Optional[ListNode]) -> None:
listStack: list[ListNode] = []
nh = head
while nh:
listStack.append(nh)
nh = nh.next
l, r = 0, len(listStack) - 1
while l < r:
listStack[l].next = listStack[r]
listStack[r].next = listStack[l+1]
l += 1
r -= 1
if len(listStack) % 2:
listStack[r].next = None
else:
listStack[r+1].next = None
@@EduarteBDO Wow nice solution!
@@EduarteBDO I think thats because you transformer a linked list problem into a list problem
@@luizferreira3986 yeah the space complexity suffers, but still a good solution. always good to have new ways to do things, even if its not the most efficient, opens up your way of thinking.
Wow, this one was harder thank it looked. Thanks again for the amazing explanations
Linkedlist pointers always make me feel like I'm a dummy. So confusing 😭
I feel you bro 🥲
Same here bro. It's been 1 year now howz it going
Makes you feel like a node yourself huh?
.
.
.
.
.
Joke was that NeetCode likes having dummy nodes in his linkedlist problems
dummy = ListNode()
Sorry, ik it was a bad joke 😭
Ya bro 🤦🏻♀️
@@DanielRodrigues-bx6lrCame here to make the same joke but yea, working with linked lists feels like I'm working with assembly
This is a great explanation. Linked list questions are generally hard for me to grasp but this vid really explains it so well and straightforward. Thank you so much!
heres my slightly different solution
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
#find middle
slow = head
fast = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
#need node before second half to split list
second = slow.next
slow.next = None
prev = None
while second:
temp = second.next
second.next = prev
prev = second
second = temp
temphead = head
while prev: #shorter if odd
temp1 = temphead.next
temp2 = prev.next
temphead.next = prev
prev.next = temp1
temphead = temp1
prev = temp2
Thanks! really helpful.. Great videos! One suggestion - Placing/explaining your drawings alongside the code would make it even easier to understand, else its usually pain going back and then again coming back to the code!
Thanks. I learn something new: break linked list into two parts using two pointers.
Your channel is soooo helpful. Bless you!
Thanks, man! Top-tier explanation. Your words just went right into my brain. Top quality.
Sometime s and f pointers points to head initially. Sometime they refers to head and head.next. Is there any marker to choose appropriate values to initialise with?
Starting slow and fast both at head works fine as well. No need to `slow, fast = head, head.next` as then you'll need to `second = slow.next` to make up for the lead fast has.
bless u
i was getting so frustrated trying to understand why he did this
Great explanation. Thanks for also mentioning the array approach to solving this problem.
conceptually this problem was easy for me. Keeping the pointers straight and where I was at in the lists at each part in the code was the problem for me.
Initially I used a deque and simply popped from front and back. Of course this has O(n) space complexity, so your solution is better :) Thanks for explaining
I did an array with 2 pointers lol.
good use of deque!
I like this problem. A good one to refresh easy subproblems for linked list.
Also, as usual - great explanation!🔥
Yeah
Great solution, however I have a question why didn't you take the general fast and slow ptr algo where in you declare fast and slow both at head? 5:25
thats how they generally work.. dont they?
@@moonlight-td8ed yeah, I don't know what I was thinking....
I used a dictionary to traverse and store the linked list nodes with index location. Then I used left and right pointers to traverse the index and reorderd by pulling the related nodes from the dictionary. It was intuitive to me and one of my first problems I could solve on my own before watching the video
i tried your method just now, it gave me a different perspective to the problem. thanks!
how did you do this?
nice, i also thought this problem reminded me of a two pointer problem so im glad im not the only one
what is the point of linked list if you are going to use another data structure with size n
i think i am having the hang of it. i mean i understand the question come up with a way to do it, after remembering palindrome problem, clear and concise:
# find middle
slow, fast = head, head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
# reverse second half(right)
pre, cur = None, slow
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
# reorder list
cur = head
while cur != pre and pre:
temp_l, temp_r = cur.next, pre.next
cur.next = pre
pre.next = temp_l if pre.next else None
cur = temp_l
pre = temp_r
slow, fast = head, head also works
its an easy data structure but the way this problem has you solve it makes it complex. so many different pointers
Thanks man I asked you yesterday and you got it up today 😍🙌🏼
my first approach was the array based which i know is not inplace, but seeing this approach really feels good especially the fast and the slow pointer one .. great
Which platforms do you suggest to draw the explanation???
Excalidraw
why the initial value of fast is head.next instead of head like the slow pointer? then you don't need to manually adjust slow pointer to slow.next outside of the while loop
My idea was to find the midpoint, remove from list and append to a stack, and keep doing this until we're down to the first element of the linked list. Then pop from stack and point cur to the popped node until stack is empty (intuition is that the mid point becomes the last node as we remove an element). It passed 9/12 test causes but timed out unfortunately since it's N^2.
stack = []
cur = head
while cur.next:
fast, slow = head, head
slowPrev = head
while fast and fast.next:
fast = fast.next.next
slowPrev = slow
slow = slow.next
slowPrev.next = slow.next
q.append(slow)
while stack:
node = stack.pop()
cur.next = node
cur = cur.next
cur.next = None
You could make it O(n) time and O(n) in space. If you just pushed the nodes after midpoint into stack. Then you can pop them back starting from head. (essentially pushing and popping into stack will reverse the later half, and then we just merge them with head to midpoint).
Recursive solution is easier
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
temp,temp1 = head,head
while temp and temp.next:
temp1 = temp
temp = temp.next
if head==temp or head.next==temp:
return
temp.next = head.next
head.next = temp
temp1.next = None
self.reorderList(temp.next)
How did you know that the fast/slow pointer would get you to the center of the list? 5:48 Is this just something you have memorized? Is there some practice I could do to more easily be able to intuit this algorithm?
Actually it's well-known algorithm, you should know this if you wanna solve LL problems. The good news is it's pretty straightforward.
you made it as simple as possible man, thanks
i dont know why but it happend to me a couple of times when i struggle with a problem i just open your video and hear hello everyone lets write some more neetcode. the idea of the solution pupup fast :))))
if yall don't understand the code at first, try drawing it out. That helped me fully understand it!
Test cases don't seem to pass if you try to create a list/array and assign values that way anyway so don't bother with the extra space option.
I used a stack instead, O(N) space of course:
def reorder_list(head):
stack = []
curr = head
while curr:
stack.append(curr)
curr = curr.next
curr = head
while True:
tmp = curr.next
nxt = stack.pop()
if curr == nxt or tmp == curr:
curr.next = None
break
curr.next = nxt
curr = curr.next
curr.next = tmp
curr = curr.next
Kind of confused...what is ultimately being returned if we dont have to do it ourself? If you return 'first' it now points to null.
To make it explicit, i used the dummy node instead and returned it.
dummy = head
//find middle,
//reverse
//merge
return dummy
hm, I think using a stack here makes the most sense imo. That way we have an easier way of tracking what we visited, though you need to create a wrapper.
```
type element struct {
idx int
node *ListNode
}
func reorderList(head *ListNode) {
mid := findMiddle(head)
midHead := reverseLinkedList(mid)
l := head
r := midHead
for l.Next != nil && r.Next != nil {
lTmp := l.Next
rTmp := r.Next
l.Next = r
r.Next = lTmp
l = lTmp
r = rTmp
}
}
func reverseLinkedList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
h := reverseLinkedList(head.Next)
head.Next.Next = head
head.Next = nil
return h
}
func findMiddle(head *ListNode) *ListNode {
slow := head
fast := head
for {
if fast == nil || fast.Next == nil {
return slow
}
fast = fast.Next.Next
slow = slow.Next
}
}
```
for those who are wondering why we starts the code with head, head.next, cos we need to get to end of the first half, point it to none, we also need access to second half, so this way it make things easier for us.
I dont know why but i found linked lists problems much harder than trees problems, despite trees are some sort of evolution of linked lists
my first attempt for this problem was a rather bruteforce lol
repeat following until head.next.next is not None:
head -> (reverse the rest of list)
so if we have 1-2-3-4-5
1 -> (5-4-3-2)
1 -> 5 -> (2-3-4)
1 -> 5 -> 2 -> (4-3)
1 -> 5 -> 2 -> 3 -> (4)
but this was too slow :(
Hi , here are two excerpts from two of your solutions for finding the middle element. two different implementations, please can you explain the difference:
#1.Reorder linkedList
#find middle
slow, fast = head, head.next
while fast and fast.next
slow=slow.next
fast = fast.next
#2. isPalidrome linkedList
#find middle(slow)
slow, fast = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
E.g. Linked list head [4,3,2,1]:
At the end of #2, slow points to [2,1]
At the end of #1, slow points to [3,2,1]
This allows him to modify head to be [4,3] by setting slow.next to None.
It's just a traversal so modifying slow will modify the original head.
In #1 the goal is to get 2 linked lists from splitting the original
@@jamessl1544
slow,fast=head,head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
prev=None
while slow:
temp=slow.next
slow.next=prev
prev=slow
slow=temp
first,second=head,prev
while second:
temp1,temp2=first.next,second.next
first.next=second
second.next=temp1
first=temp1
second=temp2
this solution doesnt seem to work. anyone has any idea why?
@@yz-me4tq
# head [4,3,2,1]
slow,fast = head,head.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# head [4,3,2,1] slow [3,2,1]
second = slow.next
prev = slow.next = None
# head [4,3] second [2,1]
while second:
tmp=second.next
second.next=prev
prev=second
second=tmp
# head [4,3] prev [1,2] reversed second
first,second=head,prev
while second:
tmp1,tmp2=first.next,second.next
first.next=second
second.next=tmp1
first,second=tmp1,tmp2
# head [4,1,3,2]
@Longchi I had the same confusion as you. Keeping both, slow and fast, pointers at the same position in the beginning works for both solutions.
Thanks alot bro for all your efforts
class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse(head):
curr=head
prev=None
while curr is not None:
temp=curr.next
curr.next=prev
prev=curr
curr=temp
return prev
def rearrangeList(head):
temp=head
while temp:
temp.next=reverse(temp.next)
temp=temp.next
return head
If we used recursion, would it still count as extra memory?
this man is truly the
the best solution online, leetcode solution doesn't explain well about how it avoids the infinite linkedlist, it just gives a magic code.
I hate linked list problems
Great solution that doesn't take extra memory! Thank you!
Give yourself a treat by doing it recursive.
Ugh. I understand finding the midpoint and reversing the second half, but merging the two does not make sense to me at all. I dont understand how the pointers are passed around and how it manipulates the head. Ive tried for days just reading through this over and over amd nothing has clicked yet.
NeetCode, could you experiment with having your drawing solution in sync while coding. Assimilation would be faster and we will know why you applied a certain logic
I just tried drawing for myself while he was coding and it helped alot in understandingthe logic
You are doing a great job! Keep it up!
Can we do this using recursion ? What would be time complexity of it ?
Really good solution, thank you.
Brilliant solution, thank you!
how do you get your leetcode editor in dark mode?
Using the top-right settings button, and change theme to Monokai
Am I the only one that lowkey likes LinkedList problems. Definitely prefer them to Trees
Another simple way to solve this with using extra space is create the array, then just alternate pop() and poll() to assemble the linked list.
at 12:00 how is second at None when the loop finishes? Is that right?
I have doubt here we are using the extra spaces aren't we like left and right linked list
No, we aren't using any extra space.
If you notice, we aren't duplicating the values.
We are just reusing the same memory allocation.
I came up with a solution that ran in quadratic time pretty quickly but it didn't get accepted on leetcode and that's why I had to watch this video
I did this question in a complete different way using an array and two pointers. I think my solution was cheating somehow but I don't really know:
def reorderList(self, head: Optional[ListNode]) -> None:
listStack: list[ListNode] = []
nh = head
while nh:
listStack.append(nh)
nh = nh.next
l, r = 0, len(listStack) - 1
while l < r:
listStack[l].next = listStack[r]
listStack[r].next = listStack[l+1]
l += 1
r -= 1
if len(listStack) % 2:
listStack[r].next = None
else:
listStack[r+1].next = None
that was amazing thank you
If it helps you to better visualize this problem, instead of fast and slow pointer you can just count all the elements first, than iterate until the size/2 or size/2+1 th element (depends if the size is even or odd).
for merging two lists, can we set first as slow (the first linked list)?
Nice explanation! Thanks!
I dont understand how input in form of "List" is taken as argument and made it behave like a Linkedlist. I think input list "head" needs to be converted first to Linkdlist first and then taken as argument.
Can someone help me explain how thing work ?
I see your confusion as the input examples may suggest that a Python list of those numbers is being passed to the function. This list is not what is really passed into the function, it simply a visualization of the values in the linked list. Head is really the first node in the linked list.
Not sure if anyone else also created a generic reverse list helper, included mid in the second half and got infinite loops. My understanding is that if we do so, there is no way of removing the connection between the first half and the reversed second half(without adding another iteration)
a generic reverse list helper could work, just need to say 'while second.next' instead of 'while second'
very nice problem and decision
thanks for the neet explanation..
Why do we need line 14 + 15? (second = slow.next) and (slow.next = None)?
Is it because we have to return in place, so the original list can't be altered?
The original list is being altered (the nodes themselves are being changed to point to different nodes). By setting second = slow.next we are storing the head of the second list. Once we have stored the head of the second list safely, we are setting slow.next = None since slow is the last node in our first list, it should be pointing to None. So for a list such as 1 -> 2 -> 3 -> 4 -> 5 -> nullptr, the new result after these 2 operations is 1 -> 2 -> 3 -> nullptr for the first list and 4 -> 5 -> nullptr for the second.
why is first fast not head or head.next.next?
Thanks man! Really appreciate that.
Can you do skyline problem leetcode?
man ur explanation ,great great
Can someone explain why fast starts from head.next, not head?
I think either way works, but syntax is a little different. If you use fast=head, you won't need to set "second = slow.next", instead second will just be slow. You can draw it out and it will be more clear! (Anyone please correct me if I'm wrong)
You can easily start with head. You just need to modify your while loop so it runs while your fast.next && fast.next.next are true.
Only changing the initial condition fast = head without changing anything else also works. I'm also confused here
@@orangethemeow this is also confusing me, did you figure out why?
@@mkum2141 Hey I figured this out if anyone in this thread still cares 5 months later. I assume by now you all have figured it out too though. ;p
How it can be so magic and so simple at same time?
void reorderList(ListNode * head)
{
vector v;
ListNode * temp=head;
while(temp!=NULL)
{
v.push_back(temp->val);
temp=temp->next;
}
ListNode * tail=head;
int start=1 , last=v.size()-1;
while(startnext=newnode1;
tail=newnode1;
tail->next=newnode;
tail=newnode;
start++;
last--;
}
if(v.size()%2==0){
ListNode * newnode1=new ListNode(v[last]);
tail->next=newnode1;
tail=newnode1;}
tail->next=NULL;
}
T.C=O(n) S.C=O(n)//this is not the optimized answer this was the first answer discussed in the video
Tha was tricky. it seemed like an easy problem but god was i wrong!
Can someone explain why slow.next =None?
the last node of first part of the linked list becomes the last node of the reordered list, so next variable of that node (whose reference is stored in the slow pointer) is initially set to None
Where are subtitles?
Could someone explain why we don’t have to actually return anything? Why is setting first=head sufficient?
Because we never modify the first one node actually, so there's always persist a link to this node in the outer world of our function.
@@countdooku681 Thank you 🙏
Because the return type is void.
Because objects are referenced types. So any change to them will be reflected to the same memory. So you don't need to return them
hi man i want to learn basics of linklist in python from where i can learn that?
You can start from here: ua-cam.com/video/FSsriWQ0qYE/v-deo.html
@@alexandreyano7809 thanks for the link!
I need to get my hand running on these fast slow pointer questions.
Can someone suggest me some similar fast slow pointer questions?
Find the middle of a linked list
Linked List Cycle
I solved it storing only half of the nodes
def reorderList(self, head: Optional[ListNode]) -> None:
list_len = 0
node = head
while node is not None:
list_len += 1
node = node.next
half: list[ListNode] = []
i = 1
j = list_len//2 - 1
node = head
while node is not None:
node_next = node.next
if i
leetcode problems are killing me
Pretty cool problem
lmao, guess what, I solved this problem and it turned out to be LeetCode daily.... What's the chance of that happening?
understood
This messed with my head
he sounded so different back then
not really lol
best ever
Yea, absolutely BEST ever!!! 👍
intelligent
esto ya no funciona :(
como?
estas
crazy
Absolute madness. I can't grasp anything. Linked lists are delusional
wamtde
Companies should no longer hire based on this stupid crap that Copilot can easily do.
While most of your videos are usually top notch, I am disappointed in this video. You do not do this algorithm justice by explaining it properly. Your lazily attempt at explaining the algorithm just gets overshadowed because “now here’s the code surely you all can understand it”. We can’t. An animation of the algorithm would’ve been helpful, instead your 5-year-old drawings were presented and we are expected to understand what’s going on.
mad cus bad
Oh my goodness. I guess you should be disappointed at yourself. To understand this problem, you simply need to know
1. traversing a linked list
2. Using slow and fast pointers to reach the midpoint of a LL
3. Reversing a LL
All these are easy level questions that have already been discussed in this channel.
You can't expect someone to explain all basic concepts in each and every problem.
And you're expressing your disappointment as if YOU are owed a detailed explanation
skill issue
hiohlihlhilhilhilhlihilhilhilhlihlihlihilhlisexz
This explanation makes zero sense.