对链表进行插入排序

插入排序的动画演示如上。从第一个元素开始，该链表能够被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中html

解题思路

插入排序算法想必你们都不陌生了，若是不了解的话来看看下面这篇博客吧java

用 Java 实现的八种经常使用排序算法算法

难点在于这是个单向链表，不能向数组同样直接从后往前遍历，所以咱们每找到一个不符合排序规则的元素，都必须从头再遍历，找到合适的插入点，而这又考察到有关链表的操做数组

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode lastNode = head, curNode = head.next;
        while(curNode != null) {
            if(lastNode.val <= curNode.val) {
                lastNode = lastNode.next;
            } else {
                ListNode preNode = dummyHead;
                while(preNode.next.val <= curNode.val) {
                    preNode = preNode.next;
                }
                lastNode.next = curNode.next;
                curNode.next = preNode.next;
                preNode.next = curNode;
            }
            curNode = lastNode.next;
        }
        return dummyHead.next;
    }
}