Insertion Sort List leetcode

Example

Given 1->3->2->0->null, return 0->1->2->3->null.

把一个个的listnode往新的排序里面插, 维护两个指针cur(原链表) node(新链表).

node始终指向新链表表头 每次插入时候遍历新链表 往后找到node.val < cur.val 中最后一个 插入cur.(新链表升序排列 后面的val比前边大)

时间复杂度是排序算法的O(n^2)，空间复杂度O(1)

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = head;
        while (cur != null) {
            ListNode node = dummy;
            while (node.next != null && node.next.val < cur.val) {//node是升序排列的 node.next > node
                node = node.next;
            }
            ListNode tem = cur.next;
            cur.next = node.next;
            node.next = cur;
            cur = tem;
        }
        return dummy.next;
    }
}