Linked List playlist: kzread.info/dash/bejne/eWSTq4-TdpO5Y5s.html

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

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!

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

@mohitsharma1981

Жыл бұрын

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.

@tbad2009

8 ай бұрын

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?

@user-he4xf2yw4z

9 ай бұрын

On leetcode at solutions section

thanks for explanation!

Great 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?

@eslamwageh4461

3 ай бұрын

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

Thank you !

thank you!!!

Is this a constant space algorithm?

this is the top down merge sort

Thanks broooo

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

@yiweikuang

6 ай бұрын

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

@NeetCode

3 жыл бұрын

lol, thats a better video idea

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

@hoixthegreat8359

11 ай бұрын

logn

You are lit!

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.

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"

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

@dailyclipmafia5041

6 ай бұрын

no

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

@KarthikNandanavanam

2 ай бұрын

I think getting mid is still 0(n)

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

@abdurrahmansinantokmak

Жыл бұрын

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

Nice

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

2 жыл бұрын

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

2 жыл бұрын

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.

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

@purrfectempire

2 жыл бұрын

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

@GeetThaker

2 жыл бұрын

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.

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

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

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

2 жыл бұрын

this is an O(1) space complexity solution

@yonahgraphics

2 жыл бұрын

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

11 ай бұрын

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.

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

@JeremAl

2 жыл бұрын

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

2 жыл бұрын

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

2 жыл бұрын

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.

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

@012345678952752

2 жыл бұрын

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.

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

2 жыл бұрын

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

2 жыл бұрын

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

2 жыл бұрын

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

2 жыл бұрын

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

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

@priyaaofficial7

5 ай бұрын

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