LeetCode 147 Insertion Sort List

遇到操作linked list的题目，先判断head或者head.next是否为空。
之后再对node数>=2的情况进行讨论。

首先回忆一下insertion sort！！！
搜索数组，如果当前的数curr小于前一个数prev，则将该数curr插入到head到prev之间的位置。

代码：

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = head, curr = head.next;
        
        while (curr != null) {
            if (curr.val >= prev.val) {
                prev = curr;
                curr = curr.next;
            } else {
                // Start from dummy and head, to find where to insert the curr node
                // Find the first node c whose val is >= curr, insert curr node before node c
                ListNode next = curr.next, p = dummy, c = dummy.next;
                while (c.val < curr.val) {
                    p = p.next;
                    c = c.next;
                }
                p.next = curr;
                curr.next = c;
                curr = next;
                prev.next = curr;
            }
        }
        
        return dummy.next;
    }
}