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;
}
}
