worth to mention that prev pointer will always point to the last sorted element so when we do prev.next = curr.next we do it to save the next nodes and to continue from the last sorted node.
Even if you don't do the extra comparison with the last element, this algorithm is still O(n) best case, but this best case happens when the initial linked list is sorted in reverse order.
after initializing the dummy node, which point to head. When assigning head to prev with (prev = head). Are you assigning the dummy node to prev or the old head to prev? 9th line
That's most likely because two first elements are not sorted, and because of a mistake in the video you keep inserting second element before itself. Try changing tmp initialization to tmp = dummy
Just got my job at Amazon and I can say without a doubt you're a major reason for that. Thank you neetcode
noice
congrats john
Congratulations! That's lots of hard work and time. Best wishes going forward!
worth to mention
that prev pointer will always point to the last sorted element
so when we do prev.next = curr.next
we do it to save the next nodes and to continue from the last sorted node.
tmp = dummy, or you will not sort first element. Dummy is not even used after it's initialized.
I just learned insertion sort, and you posted this problem. Very Thankyou !!
noice
Even if you don't do the extra comparison with the last element, this algorithm is still O(n) best case, but this best case happens when the initial linked list is sorted in reverse order.
Why not checking if temp.next is not none before actually using its .val?
Because cur.val is guaranteed to be smaller than prev.val, tmp will first reach prev before it reaches None
after initializing the dummy node, which point to head. When assigning head to prev with (prev = head). Are you assigning the dummy node to prev or the old head to prev? 9th line
old head is assigned to prev not the dummy node. This done because it's not required to check the first node , so cur node start from the second node
hello. i have a question silly but i don't know how I can proof this example and what I need to call for print in the screem the result. thank you
start iterating from the head until it becomes null and print each node's value
@@anmolbakshi7983 thank you. You're a great person
ListNode temp = head
while(temp != null){
System.out.println(temp.val)
temp = temp.next
}
Shukriya !
Beautiful explanation
11:05 Is't it crash on empty list? Line 9 (head might be None)
add the condition if(head == null) return head
Thank you! This is very clear.
Great Job, That was so helpful.
Why this code gives TLE?
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode helpHead = new ListNode(-9999, head); //without set pointer dummy.next is works
ListNode curr = head;
while (curr != null) {
ListNode prev = helpHead;
while(prev.next != null && prev.next.val
Hello, why my code in java is not correct(Time Limit Exceeded)?
ListNode dummy = head;
ListNode curr = head.next;
ListNode prev = head;
ListNode tmp = null;
while( curr != null){
if (curr.val >= prev.val){
prev = curr;
curr = curr.next;
continue;
}
tmp = head;
while(curr.val > tmp.next.val){
tmp = tmp.next;
}
prev.next = curr.next;
curr.next = tmp.next;
tmp.next = curr;
curr = prev;
}
return dummy.next;
That's most likely because two first elements are not sorted, and because of a mistake in the video you keep inserting second element before itself. Try changing tmp initialization to tmp = dummy
Hi it’s me again I am your biggest fan plz read this comment u r helping me so much
Thank You
nice explanation! thank u
you are the best!!!
super helpful
Really helpful 😀👍
👍👍❤❤⭐⭐🙌🙌
how do I get a job at fang. what do I need to learn. its been 2 years i have been unemployed
here is the ans ruclips.net/video/YYX93BWqQY8/видео.html