给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

    插入排序 算法的步骤:

    插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
    每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
    重复直到所有输入数据插入完为止。
    下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

    对链表进行插入排序。

    示例 1：
    image.png

    输入: head = [4,2,1,3]
    输出: [1,2,3,4]
    示例 2：

    输入: head = [-1,5,3,4,0]
    输出: [-1,0,3,4,5]

    提示：

    列表中的节点数在 [1, 5000]范围内
    -5000 <= Node.val <= 5000

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode() {}
    7.  *     ListNode(int val) { this.val = val; }
    8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    9.  * }
    10.  */
    11. class Solution {
    12.     public ListNode insertionSortList(ListNode head) {
    13.         if (head == null || head.next == null) return head;
    14.         ListNode dummy = new ListNode(-1, head);
    15.         //lastNode 最后一个排序好的节点, cur当前节点
    16.         ListNode lastNode = head, cur = head.next;
    17.         while (cur != null) {
    18.             //当当前值小于排序好的最后一个节点, 就要从头开始遍历，找到插入位置
    19.             if (cur.val < lastNode.val) {
    20.                 ListNode pre = dummy;
    21.                 while (pre.next.val <= cur.val) pre = pre.next;
    22.                 //pre的下一个位置就是插入点
    23.                 ListNode next = cur.next;
    24.                 cur.next = pre.next;
    25.                 pre.next = cur;
    26.                 cur = next;
    27.                 // System.out.println(lastNode.val + ">>" + cur.val);
    28.             } else { //插入到lastNode后面就行
    29.                 lastNode.next = cur;
    30.                 lastNode = lastNode.next;
    31.                 cur = cur.next;
    32.             }
    33.         }
    34.         lastNode.next = null;
    35.         return dummy.next;  
    36.     }
    37. }