came here to learn on how to sort a linkedlist then went back to learn merge sort - hated striver then went back to learn how to merge two sorted linkedlist- hated striver then went back to learn the tortoise hare method(middle) - hated striver then came back and understood everything easily - loving striver
@avengergirl_04643 ай бұрын
😮😮😮
@ThePROestRedn993 ай бұрын
If u will jump into middle of the course...This will obviously happen
@brokegod58713 ай бұрын
Why are you learning linked list when you don't even know a basic sorting algorithm?
@Ayush372622 ай бұрын
Aur phir yahi log khete hai ki bhaijaan kiya toh sab kuch, select phir bhi nahi hua...
@JyothiBomminayani2 ай бұрын
where is the video of merge two sorted linkedlist
@abbie11034 ай бұрын
You use recursion very well in real life... In L26 - I have explained this in previous lecture(L24) go watch that; In L24 - I have explained this in previous lecture go watch that; and so on... till you reach the base video; No offense, just a catch. Your videos are really good, helped me alot. Thanks👍
@xrishabh4 ай бұрын
Recursive Nature
@rushidesai28366 ай бұрын
One of the best questions on LinkedList for sure!
@HARSHBAID-m5f9 ай бұрын
Thanks for sharing brother , i am on recursion topic learning consistently , feel good that even today you upload videos consistently in this inspiring helping 1000's of people , Thanks for that and More Power to you..
@abudanish1969 ай бұрын
Understood! Man you are a Legend!!!
@IamNikhil21219 ай бұрын
Time stamps intro :- 0:00 brute force :- 0:45 Better (merge sort) :- 6:20 complexity analysis :- 19:25
@jatinpandey64539 ай бұрын
For the people who are finding to do this problem in O(1) space complexity (follow up from leetcode, coding ninja, etc): You shouldn't ! cos theres no one who does in O(1) sc either they use merge sort or create a new Linked List (with same length of input). Solution: Only way you you can do this in constant space is by using merge sort iteratively, which is again very complex solution and is of 100 lines of codes. And i dont think interviewer will give us this much time.
@jatinpandey64539 ай бұрын
the whole 100 lines of code is just passing on edge cases after edge cases i dont think you should do these but still posting the solution
@jatinpandey64539 ай бұрын
i dont know this man has achived this : public class Solution { private class MergeHelper { public ListNode newHead; public ListNode newTail; } public ListNode sortList(ListNode head) { if ( head == null || head.next == null) { return head; } ListNode dummyHeadOne = new ListNode(0); ListNode dummyHeadTwo = new ListNode(0); ListNode dummySortedHead = new ListNode(0); ListNode dummySortedLast = dummySortedHead; ListNode unvisitedNode = head; MergeHelper mergeRst = new MergeHelper(); int listLength = 0; int level = 0; while ( unvisitedNode != null && unvisitedNode.next != null ) { unvisitedNode = addNode ( dummyHeadOne, unvisitedNode, 1
@RAJADHANISH23BCE984Күн бұрын
can do insertion sort right?
@souvik33and373 ай бұрын
this person is a real legend
@jeet-smokey4 ай бұрын
Outstanding Explanation....!!!
@unknown764368 ай бұрын
Brute force solutions ListNode* sortList(ListNode* head) { vector arr; ListNode* temp = head; // Extract values from the linked list and store them in the vector while(temp != nullptr){ arr.push_back(temp->val); temp = temp->next; } // Sort the vector sort(arr.begin(), arr.end()); // Update the linked list with sorted values temp = head; for(int i = 0; temp != nullptr; i++){ temp->val = arr[i]; temp = temp->next; } return head; }
@snehashisratna90749 ай бұрын
luv the way you teach ;
@vb61636 ай бұрын
ur vid are so good keep it up bro love u see ya bye
@MohdSaquibMansoori13 күн бұрын
If the algo is using recursion then it will take s.c to be O(log n). Then it will still no an optimized version.
@sumitkumartah21067 ай бұрын
Hey striver, we can do it by using prority queue also.
but space complexity will be O(n), and in this video solution it is O(1)
@NazeerBashaShaik5 ай бұрын
Understood, thank you.
@varunshridhar13107 ай бұрын
Do we need to consider recursion stack space?
@sadiqnaqvi9917 ай бұрын
But sir, with merge sort, we are again using auxiliary space in the stack by using recursion. So by brute force or Merge sort, space is still exhausting, right?
@dakshsingh58915 ай бұрын
stack space doesn't count as auxiliary space.
@Ayush372622 ай бұрын
@@dakshsingh5891 If you don't know something, at least don't give others false information. Recursion stack space is counted as auxiliary space.
@dakshsingh58912 ай бұрын
@@Ayush37262 okk bro i didn't know!!
@HR-pz7ts23 күн бұрын
Jyada dimag lga rha h bkl
@xperthighlightАй бұрын
bro after landing in this video by following your a2z sheet , I have been redirecting like a linked list to its previous again and again until I met a base case 🤣🤣🤣🤣
@montyk.1515 ай бұрын
The question given in the sheet asks to find it in O(1) space complexity
@RAJADHANISH23BCE984Күн бұрын
impossible bro
@siddiqabr711012 күн бұрын
21:37 we're creating a new node and copying all the elements isn't that O(n) space?
@Gg696962 ай бұрын
thnx striver
@DeadPoolx1712Ай бұрын
UNDERSTOOD;
@aryasharma69Ай бұрын
S.C. will be Log(n) for using extra recursive space
@abhinavabhi356812 күн бұрын
Understood
@AshwinRB-yi3kfАй бұрын
I'm curious, why do we stop at the first middle and not the second??
@AshwinRB-yi3kfАй бұрын
Ok i figured it out, for those who didnt In the case your divided list is say 4 -> 2, the middle value according to the tortoise and hare algorithm will always be 2. This means if we divide the linked list into 2 halves left and right, left will always be equal to the original list, which results in stack overflow
@-FlyingZoro1067 ай бұрын
Thanks a lot
@_PRANAYMATE8 ай бұрын
Hey striver do we not need to count the stack space storing n function calls while calculating the space complexity
@Learnprogramming-q7f7 ай бұрын
Thank you Bhaiya
@pratyushtripathi17289 ай бұрын
Understood 😊
@prasanjit.bhanja3 ай бұрын
Legend 😊
@ArpitaChoudhury_004 ай бұрын
Thank You🙏
@YourCodeVerse8 ай бұрын
Understood✅🔥🔥
@adityasahni52626 ай бұрын
Doesn't the optimal approach takes O(logn) space as it creates logn call stacks.
@ancitamendonca732916 күн бұрын
how do the sorted lists get merged?
@arujain16905 ай бұрын
How space complexity is constant O(1) ? We are creating a new LL (dummy node) and returning it so it should be o(N) right?
@adityabhanugarg35165 ай бұрын
we are just changing pointers of already given two linked lists
@vishalgupta75224 ай бұрын
just delete the dummy node then no extra space is required
@oyeesharme3 ай бұрын
bhaiya has done some recursion here
@soumi67204 ай бұрын
the legend
@subee1289 ай бұрын
Thanks
@knowthrvdo7 ай бұрын
NICE LECTURE AND PLZ UPLOAD REMAINING LECTURES OF A TO Z SDA SHEET PLZ THEY ARE VERY HELPFULL FOR US
@Oldmonk33215 ай бұрын
🔥
@abhishekprasad0104 ай бұрын
understood
@mikeag13717 ай бұрын
merge sort also taking O(n) space i guess??
@rishabh72153 ай бұрын
can anyone explain why do we initialize Node* fast = head->next instead of just head in the tortoise-hare method?
@madhu_mohanreddy3 ай бұрын
18:50
@avengergirl_04643 ай бұрын
Bcoz as we want 1st mid in this case....if we put fast on head->next ...it will end one step early and so slow will be on 1st mid instead of 2nd mid
@ninaad7652 ай бұрын
exactly, i was confused too @avengergirl_0464 why 1st, 2nd mid? that's only if there's even number of nodes...?
@avengergirl_04642 ай бұрын
@@ninaad765 dry run urself u will understand
@nayankhuman1043Ай бұрын
understood :)
@anotherlostspiritАй бұрын
hi, I on't understand the part where we must set fast = head.getNext() to place it 1 steps ahead the slow node, and why does slow need to stops at m1, am I missing something from the video?. I've watch the "how to find middle of Linked List" too and still doesnt know why we need that adjustment. Also I'm replying your comment cuz this is the latest comment, sorry if this borders you. Have a great day sir
@charanhr64333 ай бұрын
🎉🎉
@harigs7229 күн бұрын
🎉❤
@AnshulSharma-gq2vn7 ай бұрын
❤❤
@YashGaneriwal-je6rh2 ай бұрын
done and dusted
@vinayaksai_akulaКүн бұрын
def sortLL(head): a=[] temp=head if head is None or head.next is None: return head while temp!=None: a.append(temp.data) temp=temp.next a.sort() temp=head for i in a: temp.data=i temp=temp.next return head
@prathamIsOp8 ай бұрын
C++ CODE | Leetcode Solution to Sort List: ⚡⚡ ListNode* findMiddleNode(ListNode* head) { if (head == NULL || head->next == NULL) { return head; } ListNode* slow = head; ListNode* fast = head->next; // head->next because we want slow to point to the first element/middle in the even length case while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; } // merge linked list function ListNode* merge(ListNode* list1Head, ListNode* list2Head) { ListNode* dummyNode = new ListNode(-1); // can be any value ListNode* temp = dummyNode; while (list1Head != NULL && list2Head != NULL) { if (list1Head->val val) { temp->next = list1Head; temp = list1Head; list1Head = list1Head->next; } else { temp->next = list2Head; temp = list2Head; list2Head = list2Head->next; } } // if list1 still has elements left while (list1Head != NULL) { temp->next = list1Head; temp = list1Head; list1Head = list1Head->next; } // if list2 still has elements left while (list2Head != NULL) { temp->next = list2Head; temp = list2Head; list2Head = list2Head->next; } return dummyNode->next; } // MergeSort recursive ListNode* sortList(ListNode* head) { if (head == NULL || head->next == NULL) { return head; } ListNode* mid = findMiddleNode(head); ListNode* leftHead = head; ListNode* rightHead = mid->next; mid->next = NULL; // Disconnect the left and right halves leftHead = sortList(leftHead); rightHead = sortList(rightHead); return merge(leftHead, rightHead); }
@easylearn89248 ай бұрын
can anybody tell why we do fast=head->next?? if we dont do that it gives runtime error??
@chitranshsrivastava58808 ай бұрын
Do a dry run you'll easily know why it is giving runtime error.
@shreyxnsh.148 ай бұрын
you can also do this: ListNode* slow = head; ListNode* fast = head; while(fast->next!=NULL && fast->next->next!=NULL){ fast = fast->next->next; slow = slow->next; } return slow;
@ninaad7652 ай бұрын
@@shreyxnsh.14 does that work? instead of fast=head->next? (i was thinking it should be = head)
public class Solution { public static Node sortList(Node head) { if(head==null || head.next==null){ return head; } Node ih=head; Node dh=head.next; Node ic=ih; Node dc=dh; while(dc!=null && dc.next!=null){ ic.next=dc.next; dc.next=dc.next.next; ic=ic.next; dc=dc.next; } // till now we have seperated both the lists dh=reverse(dh); // now need to merge these 2 return merge(ih,dh); } public static Node reverse(Node head){ Node curr=head; Node prev=null; while(curr!=null){ Node next=curr.next; curr.next=prev; prev=curr; curr=next; } return prev; } public static Node merge(Node left,Node right){ Node dummy=new Node(0); Node curr=dummy; while(left!=null && right!=null){ if(left.data
@cenacr0075 ай бұрын
us
@CompetitiveProgramming-b5r9 ай бұрын
Hey Striver you look chuby♥
@sanjanaaa17Ай бұрын
Personally didn't like this video. If i am spending 22 mins on your video you should explain everything and not redirect to xyz videos here and there. At least summarize the code even if it is already covered in some other video :/
@ShubhamSharma-oq4hr7 ай бұрын
I really hate when you say go back and watch it, its very annoying
@gdppwow6 ай бұрын
Just watch it and comeback.
@Lalala_17014 ай бұрын
Go back bro
@abhishekg27663 ай бұрын
Bruhhhh getting this content is really hard and he is giving it for free so stop whining and go watch it 😮💨
@Adarshrai63392 ай бұрын
Bro you want him to explain same topic again and again🤡
@siddiqabr7110Ай бұрын
0:45 I'm not bragging or anything but not in a million years i think of a brute force like these how can you come up with brute force methods 😅😅
@great.Indian.cultureАй бұрын
Bura mat manna i never understood not even a single question what u have taught so far in ur videos....