T147、对链表进行插入排序

对链表进行插入排序。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5

解

使用一个dummy节点指向head节点，这样head节点就是一个普通节点了。然后设置pre和cur一前一后2个指针，每次遍历保障per和cur有序。

public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = head, cur = head.next;
        while(cur != null){
            if(pre.val < cur.val){
                pre = cur;
                cur = cur.next;
            }else{
                ListNode p = dummy;
                while(p.next != cur && p.next.val < cur.val)
                    p = p.next;
                
                pre.next = cur.next;
                cur.next = p.next;
                p.next = cur;
                cur = pre.next;
            }
        }
        return dummy.next;
    }

作弊写法，使用list保存所有值，然后排序之后放回原链表。

 public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        List<Integer> vals = new ArrayList<>();
        ListNode temp = head;
        while(temp != null){
            vals.add(temp.val);
            temp = temp.next;
        }
        temp = head;
        Collections.sort(vals);
        int i = 0;
        while(temp != null){
            temp.val = vals.get(i++);
            temp = temp.next;
        }
        return head; 
    }