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
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.
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!
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
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?
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
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
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 :))))
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 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).
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 :(
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 } } ```
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?
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
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
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.
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.
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)
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)
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 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
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
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
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
