Sort List - Merge Sort - Leetcode 148

[@NeetCode]

Linked List playlist: kzbin.info/www/bejne/fWHCemCQe5WGaZo

[@anilalapati]

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?

[@lucasxy]

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.

[@carloslazarin]

thank you a lot!

[@JustCuter]

left = head mid = self.getMid(head) right = mid.next mid.next = None save one line of code and less confusing

[@mohitsharma1981]

Thanks

[@SURYA-w3k]

thanks

[@linli7049]

I think you are right. When I saw the nearly 100 lines of code for O(1) space complexity solution I was stunned.

[@RohithMusic]

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.

[@tbad2009]

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?

[@MichaelKao-dj9of]

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"

[@butterfly34457]

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?

[@eslamwageh4461]

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

[@jeromesimms]

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?

[@KostyaZinoview]

On leetcode at solutions section

[@kalyanvejalla]

not constant time, constant space

[@275phuongvy]

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

[@nathanx.675]

this is an O(1) space complexity solution

[@yonahgraphics]

@@nathanx.675 Nope, recursive calls: O(logn)

[@pravargupta6285]

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.

[@ivaylokostadinov7543]

@@pravargupta6285 but I think he is asking about O(1) space, not O(n)

[@hoixthegreat8359]

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.

[@lethality3704]

this is the top down merge sort

[@anmolgautam19]

what's the space complexity of this problem.? is it still O(n) or O (log n)

[@hoixthegreat8359]

logn

[@derekzhang9655]

I swear i hear league msgs in the background..... Great vid tho!

[@lewisw29]

I thought getting the mid node is O(n) so I gave up on merge sort when I thought of it lol

[@KarthikNandanavanam]

I think getting mid is still 0(n)

[@yonahgraphics]

Hey NeetCode, why does the fast pointer start at head.next? I thought they should start from the same point

[@purrfectempire]

I am confused about that one too. Let me know if you get the answer to that, please.

[@GeetThaker]

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.

[@dinesh6489]

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.

[@hoyinli7462]

excellent explanation. i love your diagrams

[@mohammadusman9975]

I saw the Robinhood logo and read it short list

[@NeetCode]

lol, thats a better video idea

[@maamounhajnajeeb209]

you made it easy man, thanks

[@henrydi800]

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

[@prashantshukla8395]

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.

[@manitbhusal1554]

I've followed the same line of code, but I'm getting the problem of maximum recursion depth.

[@JeremAl]

I think there is a mistake as pointed by YONAH GRAPHICS and fast should be set to head. Not head.next. I will test

[@012345678952752]

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

[@tianjianni840]

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.

[@Meloman0001]

Great explanation

[@VirtualKnowledgeHub]

Hello, Instead of listnodes, this code is returning the listnode object created at memory location. Please guide me, how to print entire listnode.

[@dailyclipmafia5041]

no

[@yuanthony5199]

Is this a constant space algorithm?

[@juliuscecilia6005]

For getMid function, why was fast set to head.next? In Leetcode 876. Middle of the Linked List, fast was also set to head.

[@ShubhamGupta-qk9uq]

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.

[@orangethemeow]

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

[@veliea5160]

did you get why? I am curios why? now i need to memorize that this get_middle function is different than normal one

[@DivyaSingh-bl4cj]

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

[@ruiqiyin3847]

My understanding is that we want to find the node before right, so the node from getMid belongs to the right list.

[@orangethemeow]

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

[@sanketgaikwad1399]

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

[@vulamnguyen9453]

You can think it as "current_node" that we use to track the next node in linked list

[@lucasxy]

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.

[@asdfasyakitori8514]

This runs extremely slow in Golang, I don't understand

[@AkramDevTalks]

The recursive approach takes O(logN) space. Correct me if i am wrong

[@yuriy6833]

thanks for explanation!

[@yanhuichen8119]

Can someone explain why is the memory complexity logN? Appreciate!!!

[@abdurrahmansinantokmak]

Mergesort for array O(N) space and for linked list (log n) space.

[@bandit8258]

anyone know why do we need the "and" in the getMid function? Cant we use or? Thanks

[@yiweikuang]

No. Since fast may be null, if we check fast.next, we will get an error java.lang.NullPointerException

[@poorpanda9033]

Thank you !

[@AndrewCJXing]

Could someone explain why we need a dummy? Can't we just use the tail variable and set it to null?

[@012345678952752]

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.

[@TURALOWEN]

thank you!!!

[@ronpb3943]

Thanks broooo

[@edwardteach2]

U a God

[@hamaed19]

Nice

[@heisenberg1844]

You are lit!

[@mma-dost]

How the hell people are able to understand the merge function man what's the use of dummy and tail ??

[@JohannLiebert511]

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

[@eraytasay]

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

[@priyaaofficial7]

In Java it should be like .next to traverse basically you have to traverse first to get the mid Node not .getMid()