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

示例 1

输入: 4->2->1->3
输出: 1->2->3->4

示例 2

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

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

//遍历节点,将值较小的节点从头遍历直到找到合适的位置。
class Solution {
    public static ListNode insertionSortList(ListNode head) {
        if (head == null){
            return head;
        }
        ListNode dummy = new ListNode(0);//处理链表时，在头部添加空节点能避免对第一个节点做特殊处理。
        dummy.next = head;
        ListNode checkNode = head;
        ListNode insertNode = dummy;
        ListNode temp;
        while (checkNode.next!=null){
            if (checkNode.val > checkNode.next.val){
                temp = checkNode.next;
                checkNode.next = checkNode.next.next;
                while (insertNode.next!=null){
                    if (insertNode.next.val<temp.val){
                        insertNode = insertNode.next;
                    }else{
                        temp.next = insertNode.next;
                        insertNode.next = temp;
                        insertNode = dummy;
                        break;
                    }
                }
            }else{
                checkNode = checkNode.next;
            }
        }
        return dummy.next;
    }
}

使用了双重循环，最糟糕的情况是倒序的链表，时间复杂度为 \(O(N^2)\)，只使用了常数个变量，空间复杂度为 \(O(1)\)。