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
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👍
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 🤣🤣🤣🤣
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..
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.
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
I think at 21:39 the Space Complexity won't be O(1), the reason being that the recursion stack adds up to Space Complexity of O(log N). But anyways there's no explicitly auxiliary space is being used, so the reasoning is always O(1).
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?
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
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
@@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
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
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;
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 :/
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
😮😮😮
If u will jump into middle of the course...This will obviously happen
Why are you learning linked list when you don't even know a basic sorting algorithm?
Aur phir yahi log khete hai ki bhaijaan kiya toh sab kuch, select phir bhi nahi hua...
where is the video of merge two sorted linkedlist
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👍
Recursive Nature
Obviously Why will he reexplain same thing again. its not optimal🙃
One of the best questions on LinkedList for sure!
Time stamps
intro :- 0:00
brute force :- 0:45
Better (merge sort) :- 6:20
complexity analysis :- 19:25
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 🤣🤣🤣🤣
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..
Understood! Man you are a Legend!!!
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.
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
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
can do insertion sort right?
@@RAJADHANISH23BCE984 Insertion sort will increase time complexity to O(n^2)
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;
}
this person is a real legend
ur vid are so good keep it up bro love u see ya bye
Outstanding Explanation....!!!
came here watched first three minutes.....regretted after seeing a simple soln and went back!
luv the way you teach ;
I think at 21:39 the Space Complexity won't be O(1), the reason being that the recursion stack adds up to Space Complexity of O(log N). But anyways there's no explicitly auxiliary space is being used, so the reasoning is always O(1).
isn't recursion stack O(N)? If no can you pls explain why?
whata beautiful question it is❤
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);
}
The question given in the sheet asks to find it in O(1) space complexity
impossible bro
Understood, thank you.
love the vids tho, keep it up!
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.
Hey striver, we can do it by using prority queue also.
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;
}
};
but space complexity will be O(n), and in this video solution it is O(1)
thnx striver
thank you man
Understood✅🔥🔥
Do we need to consider recursion stack space?
Understood 😊
S.C. will be Log(n) for using extra recursive space
21:37 we're creating a new node and copying all the elements isn't that O(n) space?
No since we are merging it inplace. as we are just chaging pointers using single dummy node
@yashwanthyerra2820 yeah yeah i realised it on that day when i commented this
Thank You🙏
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?
stack space doesn't count as auxiliary space.
@@dakshsingh5891 If you don't know something, at least don't give others false information.
Recursion stack space is counted as auxiliary space.
@@Ayush37262 okk bro i didn't know!!
Jyada dimag lga rha h bkl
Legend 😊
Thanks a lot
can we do it by sorting(head->next) and insert(head) at correct position using recursion
same way how we sorted a stack using recursion
understood!!!
please keep your video on the left, we're all used to it being that way ;-;
Thank you Bhaiya
🔥
UNDERSTOOD;
the legend
Thanks
how do the sorted lists get merged?
🎉🎉
Doesn't the optimal approach takes O(logn) space as it creates logn call stacks.
bhaiya has done some recursion here
❤❤
🎉❤
understood
Hey striver do we not need to count the stack space storing n function calls while calculating the space complexity
I'm curious, why do we stop at the first middle and not the second??
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
NICE LECTURE AND PLZ UPLOAD REMAINING LECTURES OF A TO Z SDA SHEET PLZ THEY ARE VERY HELPFULL FOR US
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?
we are just changing pointers of already given two linked lists
just delete the dummy node then no extra space is required
can anyone explain why do we initialize Node* fast = head->next instead of just head in the tortoise-hare method?
18:50
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
exactly, i was confused too
@avengergirl_0464 why 1st, 2nd mid? that's only if there's even number of nodes...?
@@ninaad765 dry run urself u will understand
merge sort also taking O(n) space i guess??
understood :)
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
@@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
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
can anybody tell why we do fast=head->next?? if we dont do that it gives runtime error??
Do a dry run you'll easily know why it is giving runtime error.
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;
@@shreyxnsh.14 does that work? instead of fast=head->next? (i was thinking it should be = head)
Trees please 😉
first comment
done and dusted
7:00
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);
}
};
where is the code man?
Do it dude.
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
bro i dont know why you are using reverse here.probably that might be the bug
replace reverse with recursive mergeSort
22-01-25
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;
}
Its not short!!!!!!!
us
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 :/
I really hate when you say go back and watch it, its very annoying
Just watch it and comeback.
Go back bro
Bruhhhh getting this content is really hard and he is giving it for free so stop whining and go watch it 😮💨
Bro you want him to explain same topic again and again🤡
🤡
Hey Striver you look chuby♥
Understood
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 😅😅
Bura mat manna i never understood not even a single question what u have taught so far in ur videos....
Understood
understood
Understood
understood
Understood
understood
Understood
understood