Sort List - Merge Sort - Leetcode 148 

Linked List playlist: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-G0_I-ZF0S38.html

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.

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

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.

you made it easy man, thanks

thanks for explanation!

Thank you !

Great explanation

thank you!!!

Thanks broooo

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?

this is the top down merge sort

You are lit!

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?

Is this a constant space algorithm?

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"

I saw the Robinhood logo and read it short list

Nice

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

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

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

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

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

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

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

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

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

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

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

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

U a God

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

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

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