leetcode 147. 对链表进行插入排序
这个题目需要我们使用插入排序去解决链表的排序。
思路：使用dummyHead（人造链表头）进行插入排序。
首先我们使用两个指针，一个last和一个cur进行标记，比较他们两的大小。
如果说（1）last.val <= cur.val 那么我们不需要进行排序，继续向后移动。
（2）last.val > cur.val 此时需要将cur向前进行插入，那么我们需要寻找插入的位置。
因为last及其之前的节点都已经是有序的了，那么我们就从dummyHead向后寻找那个位置，即pre(初始为dummyHead，逐渐向后寻找).next.val <= cur.val
寻找到这个位置后，我们就可以进行一番操作。
last.next = cur.next;
cur.next = pre.next;
pre.next = cur;
最后cur = last.next;
代码：
public static ListNode insertionSortList(ListNode head) {if(head == null) return head;ListNode dummyHead = new ListNode(0);dummyHead.next = head;ListNode last = head;ListNode cur = head.next;while(cur != null){if(last.val <= cur.val){last = last.next;}else {ListNode pre = dummyHead;while(pre.next.val <= cur.val) pre = pre.next;last.next = cur.next;cur.next = pre.next;pre.next = cur;}cur = last.next;}return dummyHead.next;
}