# insertion sort list

• public class Solution {
/**
*/
}

ListNode pre,curr,next;

while (curr != null) {// insert every single curr into sorted list
next = curr.next; //prepare for insertion && swapping.
pre = sortedListHead;//the list to scan
while (pre.next != null && pre.next.val <= curr.val) {
//as long as pre and its front are sorted ascending, keep going
pre = pre.next;
}
//when pre.next == null , or curr is less than a node in pre.next, we want to insert curr before that pre.next node
curr.next = pre.next;
pre.next = curr;

curr = next;//use the original next, instead of the new curr.next
}//end while

}

}

/*
Thoughts:
Look at head pointer, which is the current element we focus on.
If it's greater than the next pointer value, we move on. Use a while loop to check the entire
list every time with a new head.
If the head.val is less/equal than the next.val, we stop the at this next pointer, then cut it,
/
/
*

• Definition for ListNode.
• public class ListNode {
• int val;

• ListNode next;

• ListNode(int val) {

•     this.val = val;

•     this.next = null;

• }

• }
/
public class Solution {
/
*
*/
return null;
}
ListNode dummy = new ListNode(0);
ListNode node = dummy;
while (node.next != null && node.next.val < head.val) {
node = node.next;
}