BM12. [单链表的排序]

alt

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM12. 单链表的排序

https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=295&sfm=github&channel=nowcoder

题目分析

插入排序的时间复杂度一般来讲是O(n2)，但是题目要求的时间复杂度是O(nlogn) ，有哪些排序时间复杂度是O(nlogn) ？归并排序、堆排序、快速排序。难免想起我们的老朋友合并K个有序的链表，所以思考一下适合链表的排序可能就是归并排序。

模板一
归并 left = head right = null 采用左闭右开

//什么时候进行返回，当l的next已经触碰到了你的右边界，因为你是左闭右开的所以next == r的时候就要进行返回，这块非常的重要          //可以多想一想为什么是这样的。另外当你进行返回的时候说明找到了最小的节点，那么它的下一个节点就应该是null
    if(l.next == r){
            l.next = null;
            return l;
        }
    ListNode mergeLeftNode = mergeSort(l, mid);
    // 这块需要非常的注意就是我们使用的是左闭右开所以用的不是mid.next;
    ListNode mergeRightNode = mergeSort(mid, r);
    return mergeList(mergeLeftNode, mergeRightNode);

模板二
寻找链表中点

public ListNode getMidNode(ListNode head) { 
    if (head == null || head.next == null) {
        return head;
    }
    ListNode slow = head, fast = head.next;
    //注意这块判断条件的写法
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

第一步基本上就是拆链表，如何拆链表肯定是找到链表的中点，找到链表的中点使用的技巧基本上就是快慢指针。

public ListNode mergeSort(ListNode l, ListNode r){
        if(l == null)
            return null;
        if(l.next == r){
            l.next = null;
            return l;
        }
        ListNode slow = l;
        ListNode fast = l;
        while(fast != r){
            slow = slow.next;
            fast = fast.next;
            if(fast!= r)
            fast = fast.next;
        }
        ListNode mid = slow;
        ListNode mergeLeftNode = mergeSort(l, mid);
        ListNode mergeRightNode = mergeSort(mid, r);
        return mergeList(mergeLeftNode, mergeRightNode);  
    }

合并两个有序链表我们已经很熟练了

    public ListNode mergeList(ListNode p1, ListNode p2){
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while( p1 != null && p2!=null){
            if(p1.val < p2.val){
                p.next = p1;
                p1= p1.next;
            }else{
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if(p1 != null){
            p.next = p1;
        }
        if(p2 != null){
            p.next = p2;
        }
        return dummy.next;
    }

完整题解

 public ListNode sortInList (ListNode head) {
        return mergeSort(head, null);
    }

    //其实是一个左闭右开的情况
    public ListNode mergeSort(ListNode l, ListNode r){
        if(l == null)
            return null;
        if(l.next == r){
           l.next = null;
           return l;
        }
        ListNode slow = l;
        ListNode fast = l;
        while(fast != r){
            slow = slow.next;
            fast = fast.next;
            if(fast!= r)
            fast = fast.next;
        }
        ListNode mid = slow;
        ListNode mergeLeftNode = mergeSort(l, mid);
        ListNode mergeRightNode = mergeSort(mid, r);
        return mergeList(mergeLeftNode, mergeRightNode);  
    }

    public ListNode mergeList(ListNode p1, ListNode p2){
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while( p1 != null && p2!=null){
            if(p1.val < p2.val){
                p.next = p1;
                p1= p1.next;
            }else{
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if(p1 != null){
            p.next = p1;
        }
        if(p2 != null){
            p.next = p2;
        }
        return dummy.next;
    }

复杂度分析

时间复杂度： $O(n*log(n))$ ，归并排序的时间复杂度
空间复杂度： $O(n)$ 需要额外开辟空间返回链表