[LeetCode] Insertion Sort List

Problem:
Sort a linked list using insertion sort.
Solution:O(n*n)

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        
        ListNode cur = head.next;
        ListNode ret = head;
        ListNode pre = head;
        while(cur!=null){
            ListNode next = cur.next;
            pre.next = next;
            
            if(ret.val > cur.val){
                cur.next = ret;
                ret = cur;
            }else if(cur.val >= pre.val){
                pre.next = cur;
                pre = cur;
            }
            else
            {
                ListNode tmp = ret;
                while(tmp.next.val< cur.val){
                    tmp = tmp.next;
                }    
                cur.next = tmp.next;
                tmp.next = cur;
            }
            cur = next;
        }
        return ret;
    }
}