1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0), ptr = head;
        while (ptr != null) {
            ListNode prev = dummy;
            while (prev.next != null && prev.next.val < ptr.val) {
                prev = prev.next;
            }
            ListNode nextNode = ptr.next;
            ptr.next = prev.next;
            prev.next = ptr;
            ptr = nextNode;
        }
        return dummy.next;
    }
}

用一个list装sort好的, 一个list则是head代表的这个list. 然后prev用来遍历sort好的list, 来去找该插在哪里, 而ptr则是用来遍历head这个list.

时间复杂度: O(n^2)
空间复杂度: O(1)