leetcode148. Sort List

OpenDigg 發(fā)布于2019-08-15 13:35 / 2644人閱讀

摘要：題目要求用的時間復(fù)雜度和的空間復(fù)雜度檢索一個鏈表。那么問題就歸結(jié)為如何將鏈表分為大小相近的兩半以及如何將二者合并。之后再對折斷的鏈表分別進(jìn)行計算從而確保每一段內(nèi)的元素為有序的。

題目要求

Sort a linked list in O(n log n) time using constant space complexity.

用O(n log n)的時間復(fù)雜度和O(1)的空間復(fù)雜度檢索一個鏈表。

思路和代碼

在給出了明確的時間復(fù)雜度和空間復(fù)雜度后，我第一個想到的就是利用divide and conquer 方法進(jìn)行排序。那么問題就歸結(jié)為如何將鏈表分為大小相近的兩半以及如何將二者合并。
了解利用分治法對數(shù)組進(jìn)行排序的童鞋應(yīng)該知道，我們會根據(jù)數(shù)組的下標(biāo)將數(shù)組取一半分別進(jìn)行排序后，再將排序好的二者進(jìn)行合并。
那么將鏈表分為大小相近的兩部分則需要我們用三個指針來進(jìn)行。分別是prev, slow和fast，其中fast指針每次往前跑兩步，slow往前跑一步，這樣確保slow指針是第二部分開頭的第一個指針，而prev則是slow指針的前一個指針。prev指針是用來折斷鏈表的。

        ListNode prev = null, slow = head, fast = head;
        while(fast!=null && fast.next!=null){
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;

之后再對折斷的鏈表分別進(jìn)行計算從而確保每一段內(nèi)的元素為有序的。

之后我們需要將相鄰的兩段鏈表進(jìn)行合并，這個就很簡單了。只需要另設(shè)一個頭指針，并每次比較兩段的當(dāng)前節(jié)點，取較小的節(jié)點加入頭指針即可。

所有代碼如下：

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode prev = null, slow = head, fast = head;
        while(fast!=null && fast.next!=null){
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        return merge(l1, l2);
    }
    
    public ListNode merge(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1!=null && l2!=null){
            if(l1.val < l2.val){
                ListNode tmp = l1.next;
                cur.next = l1;
                l1.next = null;
                l1 = tmp;
            }else{
                ListNode tmp = l2.next;
                cur.next = l2;
                l2.next = null;
                l2 = tmp;
            }
            cur = cur.next;
        }
        if(l1==null) cur.next = l2;
        else cur.next = l1;
        return dummy.next;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~