147. 排序链表（基础版）

题目描述：https://leetcode-cn.com/problems/insertion-sort-list/

思路：









PS：
dummmyHead, 便于在head前插入节点，但我觉得没啥用，头插法按以下步骤执行即可：
nextNode = curNode->next;
curNode->next = head;
head = curNode;
preNode->next = nextNode;

lastSorted, 已排序链表最后元素的节点
curr，待排序节点
prev，value值比curr->value值大节点的前置节点，可理解为最终待插入位置的前置节点

完整代码（C++）：
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null) {
return head;
}
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode lastSorted = head, curr = head.next;
while (curr != null) {
if (lastSorted.val <= curr.val) {
lastSorted = lastSorted.next;
} else {
ListNode prev = dummyHead;
while (prev.next.val <= curr.val) {
prev = prev.next;
}
lastSorted.next = curr.next;
curr.next = prev.next;
prev.next = curr;
}
curr = lastSorted.next;
}
return dummyHead.next;
}
}