Leetcode: Insertion Sort List

Sort a linked list using insertion sort.
Understand the problem:
The crux of the problem is to understand what is the insertion sort. Basically, the idea of the insertion sort is for a partially sorted list, say, A[] = {1 3 4 5}, and we wanna insert 2 to the list at an appropriate position. In general, the idea of the insertion sort is for a given point i, we wanna make sure its left noes are well sorted. How to achieve this? compare A[i] with A[i -1], if less, swap. 

Solution:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) {  *         val = x;  *         next = null;  *     }  * }  */ public class Solution {     public ListNode insertionSortList(ListNode head) {         if (head == null || head.next == null) {             return head;         }                   ListNode newHead = new ListNode(Integer.MIN_VALUE);         ListNode prev = newHead;         ListNode curr = head;                   while (curr != null) {             prev = newHead;             ListNode next = curr.next;                           while (prev.next != null && prev.next.val < curr.val) {                 prev = prev.next;             }                           curr.next = prev.next;             prev.next = curr;                           curr = next;         }                   return newHead.next;     }   }