LeetCode-147. 对链表进行插入排序-Java-medium

题目链接

法一

    /**
     * 法一
     * 链表模拟直接插入排序过程
     * 最坏情况时间复杂度：O(n²)
     *
     * @param head
     * @return
     */
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(); // 头节点
        ListNode pre, cur = head, disorder;
        dummy.next = head;
        while (cur != null && cur.next != null) {
            if (cur.val <= cur.next.val) { // 未排序的节点，先和前驱比较，如果大于或者等于前驱，就不用排序了
                cur = cur.next;
                continue;
            }
            pre = dummy; // pre从头节点开始
            while (pre.next.val < cur.next.val) { // pre最终指向未排序节点应插入位置的前驱
                pre = pre.next;
            }
            disorder = cur.next; // 将未排序的节点插入对应位置
            cur.next = disorder.next;
            disorder.next = pre.next;
            pre.next = disorder;
        }
        return dummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

本地测试

        /**
         * 147. 对链表进行插入排序
         */
        lay.showTitle(147);
        Solution147 sol147 = new Solution147();
        int[] nums147 = new int[]{-1, 5, 3, 4, 0};
        ListNode head147 = new ListNode();
        head147 = listOpt.creatListByArray(head147, nums147);
        listOpt.showList(head147);
        ListNode sortHead147 = sol147.insertionSortList(head147.next);
        listOpt.showNoHeadList(sortHead147);
1
2
3
4
5
6
7
8
9
10
11