LeetCode-对链表进行插入排序

题目内容

示例分析

代码实现

    public ListNode insertionSortList(ListNode head) {
        if(head == null) return null;
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode SortedLast = head;
        ListNode cur = SortedLast.next;
        while(cur != null) {
            if(SortedLast.val <= cur.val) {
                SortedLast = SortedLast.next;
                //继续判断下一个待排序的节点
                cur = SortedLast.next;
            } else {
                //进入else说明要往前面插了
                ListNode prev = newHead;
                while(prev.next.val <= cur.val) {
                    prev = prev.next;
                }
                //有序序列中最后一个数据的后继绑上下一个待排序的数据
                SortedLast.next = cur.next;
                //插入元素的后继绑上有序序列中排在它之后的数据
                cur.next = prev.next;
                //插入元素的前一个数据的后继绑上这个插入元素
                prev.next = cur;
                //继续判断下一个待排序的节点
                cur = SortedLast.next;
            }
        }
        return newHead.next;
    }

分析与插排的联系

 关键步骤分析

我们在调整结点顺序的时候，先将 SortedLast 的后继绑住下一个待排序元素，链表是有两个域的，我习惯先绑后面，再处理前一个元素的后继。

 

分析上图的1，2，3的代码：

1.有序序列最后一个元素的后继总是与待排序序列第一个元素绑定起来，循环进else，说明待插入元素的值小于SortedLast，所以就把SortedLast的后继与下一个待插入的元素绑定。

2.不管有没有进while循环，prev的位置的值一定是刚好小于cur的值，while循环的作用就是调整prev指向刚好小于cur结点的值的前一个结点。

3.把prev的后继绑住插进来的cur，形成有序序列。

 复杂度分析

1.时间复杂度

链表的排序不像数组，这里不需要挪数据，只需要修改指向就行，但是因为链表没有所谓的下标，所以找到插入位置的下标所需的时间复杂度就是 O(n) ,n 个数据的排序，所以时间复杂度为 O(n^2).

2.空间复杂度  O(1)

本篇完！！！