public ListNode insertionSortList(ListNode head) {
ListNode cur = head;
ListNode dummy = new ListNode(0), p;
while (cur != null) {
//locate the insertion position.
p = dummy;
while (p.next != null && cur.val > p.next.val) {
p = p.next;
}
//insert between p and p.next.
ListNode pNext = p.next;
p.next = cur;
ListNode next = cur.next;
cur.next = pNext;
cur = next;
}
return dummy.next;
}
Simple and clean java code


Usually we find a descending node first, take it out and insert it into the correct position. But the above snippet actually takes out every single node and insert it, so it's not necessary to make cur.previous.next = cur.next because it's rebuilding the whole list one by one (which is not the best solution).