Sort List - Merge Sort - Leetcode 148
Vložit
- čas přidán 28. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: leetcode.com/problems/sort-list/
0:00 - Read the problem
1:10 - Drawing Explanation
6:25 - Coding solution
leetcode 148
This question was identified as a Robinhood interview question from here: github.com/xizhengszhang/Leet...
#mergesort #robinhood #python - Věda a technologie
Linked List playlist: czcams.com/video/G0_I-ZF0S38/video.html
Hi, thank you for the video, I have one query , could you please help?
Usually to find the middle of the linked list, we use slow and fast = head, why did we use fast= head.next here?
For audiences who do not understand how we connect dummy to tail node:
Basically dummy and tail are two different POINTER nodes starting at the same spot of the Linked List we created. It is more accurate to understand them as POINTER instead of nodes.
In the code we do dummy= tail= Node(), that means we created 2 different pointers starting at the same Linked List Node. Then going forward dummy node stays at the starting points, but tail pointer keeps moving forward, which is to add new nodes to the LinkedList we created.
When we do return dummy.next, we are basically returning the entire Linked List we created, but trimming the beginning dummy node, because this is not part of the list1 or list2.
thank you a lot!
I think you are right. When I saw the nearly 100 lines of code for O(1) space complexity solution I was stunned.
left = head
mid = self.getMid(head)
right = mid.next
mid.next = None
save one line of code and less confusing
Thanks
excellent explanation. i love your diagrams
This has O(log(n)) space complexity due to the recursion. Merge sort can be done iteratively log(n) times to get O(1) space complexity. Note that this is possible because we are using Linked list. If we were using an array we would need O(n) additional space anyway.
space complexity in this code and any merge sort where we make new arrays (or linked lists) at each step is O(n)? why do you think it's O(log(n)) here?
you made it easy man, thanks
I'm interested to see the constant time solution that you mentioned 1:00 and I'm wondering if anyone knows where I could see it?
On leetcode at solutions section
thanks for explanation!
Why is the initialization step in getMid() function slow, fast = head, head.next and not slow, fast = head, head like in the 876. Middle of the Linked List code?
as here in this problem to get the middle node of linked list of 4 nodes we want to get the second node not the third like the 876 problem
so he made the fast proceeds with one node to do this .
trace a case of 4 node and you will get it
Great explanation
Is this a constant space algorithm?
Thank you !
thank you!!!
what's the space complexity of this problem.? is it still O(n) or O (log n)
logn
what will it return for tail=dummy=ListNdoe()?
Why do we use dummy.next as a final return? Because I do not think the code modified anything for dummy.next
When we are writing tail=dummy=ListNode() we are creating a list with the first element as (0,-1, whatever, here they are automatically created as 0) and so,then the element that comes after that is added to tail.next.............and we are dummy.next to exclude that first element that we had initially created,if you don't do that you will end up with one or many(here many) 0 as new nodes...
Hope it clears your query.
this is the top down merge sort
can you make video solving this problem with 0(1) space complexity? because in the interview, they always expect you to come up with optimal solution. Anyway, Thank you for your great explanation
this is an O(1) space complexity solution
@@nathanx.675 Nope, recursive calls: O(logn)
Well I did it in O(n) space complexity but time complexity became O(n^2), So maybe not worth it? Well it was insertion sort.
@@pravargupta6285 but I think he is asking about O(1) space, not O(n)
I don't think any interviewer will mind, so long as you note it is possible by making your code iterative. O(1) and O(logn) are so absurdly close it doesn't really matter. For a list of 4294967296 elements, the space complexity is only 32 times bigger versus the O(1) solution, whereas something with O(n) space would be 4294967296 times bigger.
Not sure if something went wrong when I'm duplicating this code. But I met an error "RecursionError: maximum recursion depth exceeded". Fixed it by considering the boundary case: "
if not head:
return None
if head.next == None:
return head"
When we define dummy and tail, how are they related to each other? Why do we not need to write dummy.next = tail? The code always works with or without that condition
dummy.next = tail is not written any where in code it actually dummy was only used to store the head for the sorted link list and primarily it was initalized with tail but tail kept on growing and last when we wanted to return head of the list we returned dummy.next
You can think it as "current_node" that we use to track the next node in linked list
so if you do dummy= Node(), tail = Node() separately, you need that condition dummy = tail.
But in the code we do dummy= tail= Node(), that means we created 2 different pointers starting at the same Linked List Node. Then going forward dummy node stays at the starting points, but tail pointer keeps moving forward to the new node, adding new nodes to the LinkedList we created.
When we do return dummy.next, we are basically returning the entire Linked List, but trimming the beginning dummy node, because this is not part of the list1 or list2.
anyone know why do we need the "and" in the getMid function? Cant we use or? Thanks
No. Since fast may be null, if we check fast.next, we will get an error java.lang.NullPointerException
I saw the Robinhood logo and read it short list
lol, thats a better video idea
Thanks broooo
Hello,
Instead of listnodes, this code is returning the listnode object created at memory location.
Please guide me, how to print entire listnode.
no
Hey NeetCode, why does the fast pointer start at head.next? I thought they should start from the same point
I am confused about that one too. Let me know if you get the answer to that, please.
This is because, if there are even number of element in linked list, then there are two middle point, so using head.next for faster pointer, slow will stop at first middle point. for example 1->2->3->4, then slow will stop at 2. If we do not start our fast with head.next then slow will stop at 3. However it is not necessary here to do fast = head.next.
slow, fast=head,head
while fast.next and fast.next.next:
slow=slow.next
fast=fast.next.next
return slow
It was working for odd and even. submitted successfully in Leetcode. Its better to have fast and slow at the head. we cant keep on changing for different problems. In cyclic prob we had fast and slow at head. So its better to change the condition based on requirements.
Can someone explain why is the memory complexity logN? Appreciate!!!
Mergesort for array O(N) space and for linked list (log n) space.
I thought getting the mid node is O(n) so I gave up on merge sort when I thought of it lol
I think getting mid is still 0(n)
This runs extremely slow in Golang, I don't understand
I've followed the same line of code, but I'm getting the problem of maximum recursion depth.
I think there is a mistake as pointed by YONAH GRAPHICS and fast should be set to head. Not head.next. I will test
@@JeremAl fast should point to head.next as mentioned in the video. It works for me. SO he might be have made some other mistake, because it shouldn't fail.
I forgot the base case (if not head or not head.next) and had the same issue. After adding that, problem of maximum recursion depth was fixed.
I swear i hear league msgs in the background..... Great vid tho!
For getMid function, why was fast set to head.next? In Leetcode 876. Middle of the Linked List, fast was also set to head.
that is also fine as it will always give second middle number for even length LinkedList but as he said this solution assumes first one being the mid so it will cause recursion error if you go with head for fast.
I did it as slow, fast = head, head at first, I got an out of range error. No matter if you use head or head.next as initial value for fast, slow always stops at the same node
did you get why? I am curios why? now i need to memorize that this get_middle function is different than normal one
@@veliea5160 they both work in same manner of you see little more you will find out while condition in in both type of program is different .
Fast, slow = heda,head
While fast.next and fast.next.next
......
While loop difference both will return same thing .. it's just different way of writing
My understanding is that we want to find the node before right, so the node from getMid belongs to the right list.
Could someone explain why we need a dummy? Can't we just use the tail variable and set it to null?
if you set tail = None, how would you set tail.next? You will get an error because a None object doesn't have "next" attribute. The ListNode object contains the "next" attribute.
You use the dummy node because in the beginning, to assign smallest node as the first node, you need to check the 1st node of the left side and the 1st node of the right side. Whichever is smallest becomes tail.next.
You are lit!
Nice
U a God
The recursive approach takes O(logN) space. Correct me if i am wrong
How the hell people are able to understand the merge function man what's the use of dummy and tail ??
java code:
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode left = head;
ListNode right = getMid(head);
ListNode tmp = right.next;
right.next = null;
right = tmp;
left = sortList(left);
right = sortList(right);
return merge(left, right);
}
private ListNode getMid(ListNode head) {
ListNode slow = head, fast = head;
ListNode tmp = head;
while (fast != null && fast.next != null) {
tmp = slow;
slow = slow.next;
fast = fast.next.next;
}
return tmp;
}
private ListNode merge(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode tail = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
if (list1 != null) {
tail.next = list1;
} else if (list2 != null) {
tail.next = list2;
}
return dummy.next;
}
}
This code does not work. getMid() is wrong. It should be like this in Java:
private static Node findMiddle(Node head)
{
var slow = head;
var fast = head;
while (fast.getNext() != null && fast.getNext().getNext() != null) {
slow = slow.getNext();
fast = fast.getNext().getNext();
}
return slow;
}
In Java it should be like .next to traverse basically you have to traverse first to get the mid Node not .getMid()