Insertion Sort List

Sort a linked list using insertion sort.

Solution: 
What is insertion sort???

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode sortedHead = new ListNode(0);
        ListNode cur = head;
        
        while(cur != null){
            ListNode nt = cur.next;
            if(sortedHead.next == null){
                sortedHead.next = cur;
                cur.next = null;
            }
            else{
                // search from the beginning 
                ListNode prev = sortedHead;
                ListNode tmp = sortedHead.next;
                while(tmp != null && cur.val > tmp.val){
                    prev = prev.next;
                    tmp = tmp.next;
                }
                // append at the end
                if(tmp == null){
                    prev.next = cur; 
                    cur.next = null;
                }
                else{
                    cur.next = tmp;
                    prev.next = cur;
                }
            }
            cur = nt;
        }
        return sortedHead.next;
    }
}