i did a similar question. it was leetcode 2095, "delete the middle node of a linked list" from leetcode 75. initially, i counted the nodes and from there, i found out where the middle node was by taking the count / 2 and then went through the linked list again to delete the middle node. i then tried the slow and fast pointer approach, but to my surprise, it resulted in near identical runtimes (2 ms difference) and memory usage. i assumed the slow and fast pointer approach would be faster since we only pass through the linked list once. edit: i realized after rewatching the video that we technically pass through the linked list twice. so, it makes sense why it resulted in identical results.
Thanks! In case any of you are wondering what to do if the definition of Middle Element changes for a linked list with even number of elements, i.e. if in the linked list with values [1,2,3,4,5,6], the middle element is 3 and not 4 as given in the problem, here's the solution with two pointer method: public class Solution { public ListNode MiddleNode(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast.next!=null && fast.next.next!=null){ slow = slow.next; fast = fast.next.next; } return slow; } }
I was wondering about that too and I actually came up with that solution first but it also worked without checking .next and .next.next. And I dont get why. Cause if the fast pointer is at 5, we need to move one more element or return slow.next, but in my case im always returning slow and it still passes. Also strange that it takes 0 ms.
Oh no im getting it, because we only check for .next != null that means even if its even and .next.next is null, we can still move the fast pointer since .next isnt null that means slow would also move and end up exactly where we want it to be, namely at the 2nd middle element. And the important thing to know: It doesnt matter wether .next.next is out of bounds. We can move the pointer anyways, it will just be null!! but thats the important difference between list and arrays. cause with arrays, you cant do that as it would throw an exception. with ll, you can!
It's funny working through Grind 75, I think we used a similar approach to account for cycles in a linkedlist and where to break out of it, I think it was 141
Thanks for the video explanation, and I understand conceptually why it works and how to implement it in code (typescript in my case). Where I'm lost is the given input and output values. Can you please explain why in the question it gives the input and output as an array of numbers even though the class is ListNode, which is clearly defined as not simply an array of numbers? I really don't understand.
if the middle node is defined as i=n/2 starting with i==0, then this method stops one node short of middle. For n == 8, middle node index == 4. But when fast pointer is at i == 6 and slow is at i == 3, (fast && fast->next) becomes false, so we stop.
I solved it similarly in java and I got a NullPointerExpection because fast.next.next is not defined. What if the fast.next is the last node? So I solved by splitting that line into two parts, this is the whole logic I wrote: while(fast != null && fast.next != null){ fast = fast.next; if(fast == null) break; if(fast.next != null) fast = fast.next; slow = slow.next; }
i can see why you may think that, but we don't necessarily measure the actual time an algorithm takes. so O(n/2) reduces to O(n) because we remove all constants.
i cant understand why we wrote while fast and fast.next: What does it mean? While fast and fast.next != what? !=0 or !=True? how we can rewrite it to understand better
i did a similar question. it was leetcode 2095, "delete the middle node of a linked list" from leetcode 75. initially, i counted the nodes and from there, i found out where the middle node was by taking the count / 2 and then went through the linked list again to delete the middle node. i then tried the slow and fast pointer approach, but to my surprise, it resulted in near identical runtimes (2 ms difference) and memory usage. i assumed the slow and fast pointer approach would be faster since we only pass through the linked list once.
edit: i realized after rewatching the video that we technically pass through the linked list twice. so, it makes sense why it resulted in identical results.
Thanks!
In case any of you are wondering what to do if the definition of Middle Element changes for a linked list with even number of elements, i.e. if in the linked list with values [1,2,3,4,5,6], the middle element is 3 and not 4 as given in the problem, here's the solution with two pointer method:
public class Solution {
public ListNode MiddleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast.next!=null && fast.next.next!=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
I was wondering about that too and I actually came up with that solution first but it also worked without checking .next and .next.next.
And I dont get why.
Cause if the fast pointer is at 5, we need to move one more element or return slow.next, but in my case im always returning slow and it still passes.
Also strange that it takes 0 ms.
Oh no im getting it, because we only check for .next != null that means even if its even and .next.next is null, we can still move the fast pointer since .next isnt null that means slow would also move and end up exactly where we want it to be, namely at the 2nd middle element.
And the important thing to know: It doesnt matter wether .next.next is out of bounds. We can move the pointer anyways, it will just be null!! but thats the important difference between list and arrays. cause with arrays, you cant do that as it would throw an exception. with ll, you can!
awesome thank you so much for all of your clean and simple code solution explanation.
definetly a neet code!!
It's funny working through Grind 75, I think we used a similar approach to account for cycles in a linkedlist and where to break out of it, I think it was 141
I was always wondering why they use fast and fast.next, I traced it saw the solution and was still confused, thankyou for this.
Thanks for the video explanation, and I understand conceptually why it works and how to implement it in code (typescript in my case). Where I'm lost is the given input and output values. Can you please explain why in the question it gives the input and output as an array of numbers even though the class is ListNode, which is clearly defined as not simply an array of numbers? I really don't understand.
It's just a representation of a linked list, you can quickly see the expected value and the order of their nodes in that representation.
if the middle node is defined as i=n/2 starting with i==0, then this method stops one node short of middle.
For n == 8, middle node index == 4. But when fast pointer is at i == 6 and slow is at i == 3, (fast && fast->next) becomes false, so we stop.
Thanks. Keep uploading videos!
Hi Neetcode, can we get weekly contest solution video.
Hi Neetcode, Thank you for a great solution. is it your next channel?
I solved it similarly in java and I got a NullPointerExpection because fast.next.next is not defined.
What if the fast.next is the last node?
So I solved by splitting that line into two parts, this is the whole logic I wrote:
while(fast != null && fast.next != null){
fast = fast.next;
if(fast == null)
break;
if(fast.next != null)
fast = fast.next;
slow = slow.next;
}
Coooll.............
God
Can you explain also worst and best case scenario , and big O notation
He explains it in the video....
eu acho que seria O(N/2)
i can see why you may think that, but we don't necessarily measure the actual time an algorithm takes. so O(n/2) reduces to O(n) because we remove all constants.
i cant understand why we wrote while fast and fast.next: What does it mean? While fast and fast.next != what? !=0 or !=True? how we can rewrite it to understand better
It’s written to check whether they are NONE or not, cos if it’s none then we are at the end of the linked list and the loop is terminated
Writing "while fast" is the same as writing "while fast == True". If "fast" is pointing to a node its considered True.
it's Python's way of saying fast.next is not None
Stop. It's not a real neetcode. What the f?