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:

/**
 * 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;
    }

}