Insertion Sort List LeetCode solution in Java

1
class Solution {
2
  public ListNode insertionSortList(ListNode head) {
3
    ListNode cur = head;
4
    ListNode temp = new ListNode(-5001);
5
    ListNode prev = temp;
6
    while (cur != null) {
7
      ListNode nxt = cur.next;
8
      if (prev.val >= cur.val) prev = temp;
9
      while (prev.next != null && prev.next.val < cur.val) prev = prev.next;
10
      cur.next = prev.next;
11
      prev.next = cur;
12
      cur = nxt;
13
    }
14
    return temp.next;
15
  }
16
}