[leetcode-排序]--147. Insertion Sort List

小咪咪 2022-07-12 00:25 178阅读 0赞

Question147. Insertion Sort List

> Sort a linked list using insertion sort.
> 
> 中文：使用插入排序来让链表有序。

解决思路：在新链表的head结点之前构建一个结点，然后将所有的结点依次插入在helper结点之后，最后返回helper.next 结点即是排序后的新链表的首结点。

实现源码：

/** * 核心思想是在head前面构造一个helper结点 * @param head * @return */
    public static ListNode insertionSortList2(ListNode head) {
        if( head == null ){
            return head;
        }
    
        ListNode helper = new ListNode(0); //构造一个结点, 该节点不算入实际的数据链表中,仅仅把其next指向最后的head
        ListNode cur = head; //将插入的结点
        ListNode pre = helper; //在pre和pre.next之间插入结点
        ListNode next = null; //下一个将被插入的结点
    
        //遍历原链表
        while( cur != null ){
            //保存下一个结点
            next = cur.next;
    
            //find the right place to insert
            while( pre.next != null && pre.next.val < cur.val ){
                pre = pre.next;
            }
            //将cur插入在pre 和 pre.next之间
            cur.next = pre.next;
            pre.next = cur;
    
            //pre归位helper
            pre = helper;
            //cur后移
            cur = next;
        }
        return helper.next;
    }

上诉排序的时间复杂度不难分析得出是O(n^2)。

测试用例：

public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode n1 = new ListNode(2);
        ListNode n2 = new ListNode(4);
        ListNode n3 = new ListNode(1);
        ListNode n4 = new ListNode(3);
        head.next = n1;
        n1.next = n2;
        n2.next=n3;
        n3.next=n4;
    
        ListNode h =  insertionSortList2(head);
    
        while (h!=null){
            System.out.println(h.val);
            h = h.next;
        }
    
    }

输出：

0,1,2,3,4,

### 从这题里面学到的思路： ###

>  对于链表的插入，可以试着构造一个虚拟的结点作为head的前结点，这样无形中就给head构造了一个前结点pre，会非常方便链表插入时的比较。