Leetcode 147. Insertion Sort Lis

Sort a linked list using insertion sort.

题意：用插入排序的方法排序一个链表。

思路：

1. 重启一个头结点指向新链表。

2. 遍历待排序的链表，对每个带排序的节点a，在新链表中找第一个比a大的节点b。

3. 将a插入到新链表，需要借助一个辅助指针pre。

    public ListNode insertionSortList(ListNode head) {
    if (head == null) {
        return null;
    }
   
    ListNode newHead = new ListNode(0);
    ListNode node = head;
    while (node != null) {
        ListNode newNode = new ListNode(node.val);
        if (newHead.next == null) {
            newHead.next = newNode;
        } else {
            //find first bigger
            ListNode pre = newHead;
            ListNode dummy = newHead.next;
            while (dummy != null && dummy.val < node.val) {
                pre = pre.next;
                dummy = dummy.next;
            }
            //insert
            pre.next = newNode;
            newNode.next = dummy;
        }
        node = node.next;
    }
   
    return newHead.next;
    }