147. Insertion Sort List

二刷
 64.94 % 
class Solution {
    public ListNode insertionSortList(ListNode head) {
        // prev              curr     next
        // 0  -> 2 ->   4      2     ->1    ->3
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        ListNode curr = head;
        ListNode next = null;
        while (curr != null) {
            prev = dummy;
            while (prev.next != null && prev.next.val < curr.val) {
                prev = prev.next;
            }
            next = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = next;
        }
        return dummy.next;
    }
}
 一刷
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        ListNode newCurr = dummy;
        ListNode oldCurr = head;
        ListNode oldTemp = null;
        while (oldCurr != null) {
            newCurr = dummy;
            while (newCurr.next != null && newCurr.next.val < oldCurr.val) {
                newCurr = newCurr.next;
            }
            oldTemp = oldCurr.next;
            oldCurr.next = newCurr.next;
            newCurr.next = oldCurr;
            oldCurr = oldTemp;
         
        }
        return dummy.next;
    }
}