Leetcode/各大家 -- 147. Insertion Sort List

147. Insertion Sort List（2 Ptr）
Medium
https://leetcode.com/problems/insertion-sort-list/?tab=Description
Sort a linked list using insertion sort.

思路： Use dummy head to point sorted list. Maintain 2 parts: sorted | unsorted.
          Use 2 ptr(cur-> current element & pre -> end of sorted list). When meeting invalid cur,
          Insert cur into sorted list by comparing with dummy head

Complexity: Time O(N^2) Space O(1)

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode pre = head;
        ListNode cur = head;
        dummy.next = pre;
        while(cur != null){
            if(pre.val > cur.val){
                pre.next = cur.next;
                ListNode headN = dummy;
                while(headN.next != null && headN.next.val < cur.val){
                    headN = headN.next;
                }
                cur.next = headN.next;
                headN.next = cur;
                cur = pre.next;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}