L26. Sort a Linked List | Merge Sort and Brute Force

[@mohammadusman9701]

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_0464]

😮😮😮

[@ThePROestRedn99]

If u will jump into middle of the course...This will obviously happen

[@brokegod5871]

Why are you learning linked list when you don't even know a basic sorting algorithm?

[@Ayush37262]

Aur phir yahi log khete hai ki bhaijaan kiya toh sab kuch, select phir bhi nahi hua...

[@JyothiBomminayani]

where is the video of merge two sorted linkedlist

[@abbie1103]

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👍

[@xrishabh]

Recursive Nature

[@rushidesai2836]

One of the best questions on LinkedList for sure!

[@IamNikhil2121]

Time stamps intro :- 0:00 brute force :- 0:45 Better (merge sort) :- 6:20 complexity analysis :- 19:25

[@HARSHBAID-m5f]

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..

[@abudanish196]

Understood! Man you are a Legend!!!

[@jatinpandey6453]

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.

[@jatinpandey6453]

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

[@jatinpandey6453]

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?

[@yashwanthyerra2820]

@@RAJADHANISH23BCE984 Insertion sort will increase time complexity to O(n^2)

[@unknown76436]

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; }

[@souvik33and37]

this person is a real legend

[@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 🤣🤣🤣🤣

[@atharvalole4912]

came here watched first three minutes.....regretted after seeing a simple soln and went back!

[@jeet-smokey]

Outstanding Explanation....!!!

[@montyk.151]

The question given in the sheet asks to find it in O(1) space complexity

[@RAJADHANISH23BCE984]

impossible bro

[@aryasharma69]

S.C. will be Log(n) for using extra recursive space

[@snehashisratna9074]

luv the way you teach ;

[@MohdSaquibMansoori]

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.

[@varunshridhar1310]

Do we need to consider recursion stack space?

[@sadiqnaqvi991]

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?

[@dakshsingh5891]

stack space doesn't count as auxiliary space.

[@Ayush37262]

​@@dakshsingh5891 If you don't know something, at least don't give others false information. Recursion stack space is counted as auxiliary space.

[@dakshsingh5891]

@@Ayush37262 okk bro i didn't know!!

[@HR-pz7ts]

Jyada dimag lga rha h bkl

[@sumitkumartah2106]

Hey striver, we can do it by using prority queue also.

[@Satyam-je4tb]

class Solution { public: ListNode* sortList(ListNode* head) { priority_queue pq; ListNode* temp = head; while(temp != NULL) { pq.push(temp->val); temp = temp->next; } temp = head; while(temp != NULL && !pq.empty()) { int top = pq.top(); pq.pop(); temp->val = top; temp = temp->next; } return head; } };

[@shifteditz06]

but space complexity will be O(n), and in this video solution it is O(1)

[@NazeerBashaShaik]

Understood, thank you.

[@vb6163]

ur vid are so good keep it up bro love u see ya bye

[@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

[@Gg69696]

thnx striver

[@adityasahni5262]

Doesn't the optimal approach takes O(logn) space as it creates logn call stacks.

[@_PRANAYMATE]

Hey striver do we not need to count the stack space storing n function calls while calculating the space complexity

[@knowthrvdo]

NICE LECTURE AND PLZ UPLOAD REMAINING LECTURES OF A TO Z SDA SHEET PLZ THEY ARE VERY HELPFULL FOR US

[@Oldmonk3321]

🔥

[@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

[@ancitamendonca7329]

how do the sorted lists get merged?

[@-FlyingZoro106]

Thanks a lot

[@DeadPoolx1712]

UNDERSTOOD;

[@oyeesharme]

bhaiya has done some recursion here

[@Learnprogramming-q7f]

Thank you Bhaiya

[@arujain1690]

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?

[@adityabhanugarg3516]

we are just changing pointers of already given two linked lists

[@vishalgupta7522]

just delete the dummy node then no extra space is required

[@pratyushtripathi1728]

Understood 😊

[@ArpitaChoudhury_00]

Thank You🙏

[@prathamIsOp]

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); }

[@YourCodeVerse]

Understood✅🔥🔥

[@prasanjit.bhanja]

Legend 😊

[@mikeag1371]

merge sort also taking O(n) space i guess??

[@siddiqabr7110]

21:37 we're creating a new node and copying all the elements isn't that O(n) space?

[@yashwanthyerra2820]

No since we are merging it inplace. as we are just chaging pointers using single dummy node

[@siddiqabr7110]

@yashwanthyerra2820 yeah yeah i realised it on that day when i commented this

[@charanhr6433]

🎉🎉

[@soumi6720]

the legend

[@harigs72]

🎉❤

[@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 😅😅

[@subee128]

Thanks

[@AnshulSharma-gq2vn]

❤❤

[@rishabh7215]

can anyone explain why do we initialize Node* fast = head->next instead of just head in the tortoise-hare method?

[@madhu_mohanreddy]

18:50

[@avengergirl_0464]

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

[@ninaad765]

exactly, i was confused too @avengergirl_0464 why 1st, 2nd mid? that's only if there's even number of nodes...?

[@avengergirl_0464]

@@ninaad765 dry run urself u will understand

[@abhinanda7049]

understood

[@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

[@shobhitmishra739]

​@@anotherlostspirit 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

[@easylearn8924]

can anybody tell why we do fast=head->next?? if we dont do that it gives runtime error??

[@chitranshsrivastava5880]

Do a dry run you'll easily know why it is giving runtime error.

[@shreyxnsh.14]

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;

[@ninaad765]

@@shreyxnsh.14 does that work? instead of fast=head->next? (i was thinking it should be = head)

[@mohitsingh7793]

class Solution { public: ListNode* findMiddle(ListNode *head) { ListNode *slow,*fast,*temp; temp=slow=fast=head; while(fast && fast->next) { temp=slow; slow=slow->next; fast=fast->next->next; } if(!fast) return temp; return slow; } ListNode *merge(ListNode *listA,ListNode *listB) { ListNode *head=new ListNode(); ListNode *root=head; while(listA && listB) { if(listA->valval) { head->next=listA; listA=listA->next; } else { head->next=listB; listB=listB->next; } head=head->next; } while(listA) { head->next=listA; listA=listA->next; head=head->next; } while(listB) { head->next=listB; listB=listB->next; head=head->next; } return root->next; } ListNode *mergeSort(ListNode * head) { if(!head || !head->next) return head; ListNode *middle=findMiddle(head); ListNode *leftHead=head; ListNode *rightHead=middle->next; middle->next=NULL; leftHead=mergeSort(leftHead); rightHead=mergeSort(rightHead); return merge(leftHead,rightHead); } ListNode* sortList(ListNode* head) { return mergeSort(head); } };

[@YashGaneriwal-je6rh]

done and dusted

[@nitpBlogs]

Trees please 😉

[@PawanKumar-hq6dy]

will this be taking NLOGN time compelexity and O(N) space public ListNode sortList(ListNode head) { if(head == null || head.next == null) return head; ListNode dummy = new ListNode(); ListNode dummyHead = dummy; ListNode temp =head; PriorityQueue pq = new PriorityQueue((a,b)-> a.val-b.val); while(temp!=null){ pq.add(temp); temp = temp.next; } while(!pq.isEmpty()){ // System.out.println(pq.peek().val); ListNode next = pq.poll(); next.next = null; dummy.next = next; dummy = dummy.next; } return dummyHead.next; }

[@rs-oz9jk]

where is the code man?

[@NarutoUzumaki-zv4wm]

Do it dude.

[@lifehustlers164]

first comment

[@IBMX65]

7:00

[@Anonymous____________A721]

Its not short!!!!!!!

[@VarunSharma-xd8xd]

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

[@yashwanthyerra2820]

bro i dont know why you are using reverse here.probably that might be the bug

[@yashwanthyerra2820]

replace reverse with recursive mergeSort

[@cenacr007]

us

[@CompetitiveProgramming-b5r]

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-oq4hr]

I really hate when you say go back and watch it, its very annoying

[@gdppwow]

Just watch it and comeback.

[@Lalala_1701]

Go back bro

[@abhishekg2766]

Bruhhhh getting this content is really hard and he is giving it for free so stop whining and go watch it 😮‍💨

[@Adarshrai6339]

Bro you want him to explain same topic again and again🤡

[@irfanmohammad2132]

🤡

[@SibiRanganathL]

Understood

[@great.Indian.culture]

Bura mat manna i never understood not even a single question what u have taught so far in ur videos....

[@dewanandkumar8589]

Understood

[@ramakrishnakcr4417]

understood

[@arnabkundu1648]

Understood

[@hardikpatel352]

understood

[@abhinavabhi3568]

Understood

[@abhishekprasad010]

understood