题目描述

对链表进行插入排序。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

样例

输入: -1->5->3->4->0
输出: -1->0->3->4->5

算法1

(插入排序) $O(n^2)$

* 构造一个虚拟头节点，来建一条新链表，每次在新建的链表中找出第一个比待插入节点大的节点和前一个节点。
* 时间复杂度：遍历n个节点，且每次插入的时候都需要遍历新链表寻找合适的插入位置，最坏情况找n次。

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) {
        ListNode dummy = new ListNode(0);
        while(head != null){
            ListNode cur = dummy;
            ListNode tmp = head.next;
            //找到第一个比head大的点的前一个点
            while(cur.next != null && cur.next.val <= head.val) cur = cur.next;
            head.next = cur.next;
            cur.next = head;
            head = tmp;
        }
        return dummy.next;
    }
}