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