leetcode--05. 链表插入排序

题目：
Sort a linked list using insertion sort
使用插入排序对链接列表进行排序

思路：
新建一个链表,遍历原链表，将每个节点加入新链表正确的位置

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        //哑节点
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode cur = head;
        ListNode pre = dummy;
        while (cur != null) {
            //保存当前节点下一个节点
            ListNode next = cur.next;
            pre = dummy;
            //寻找当前节点正确位置的一个节点
            while (pre.next != null && pre.next.val < cur.val) {
                pre = pre.next;
            }
            //将当前节点加入新链表中
            cur.next = pre.next;
            pre.next = cur;
            //处理下一个节点
            cur = next;
        }
        return dummy.next;
    }
}