Sort List

今天是一道有關排序的題目，來自LeetCode，難度為Medium，Acceptance為27%。

題目如下

Sort a linked list in O(n log n) time using constant space complexity.
Example
Given 1-3->2->null, sort it to 1->2->3->null.

解題思路及代碼見閱讀原文

回復0000查看更多題目

解題思路

首先，看到排序我們先來回憶一下學過了排序算法。

• 冒泡排序、選擇排序、插入排序，時間復雜度為O(n^2);
• 快速排序、歸并排序、堆排序，時間復雜度為O(nlogn);
• 基數(shù)排序、計數(shù)排序，時間復雜度都是O(n)。

那么，這里的算法對于數(shù)組都適用，但對于單向鏈表不一定適用。在該題中要求時間復雜度為O(nlogn)，因此我們可以從快速排序、歸并排序、堆排序中選擇，看看有沒有一種適合這里的情況。

• 快速排序，快排需要一個指針從前往后，另一個指針從后向前，但是這里用的是單向鏈表，無法快速的從后向前遍歷，因此快速排序不適用這里的場景。
• 堆排序， 堆排序在排序的過程中需要比較第i個元素和第2 * i + 1個元素的大小，需要隨機訪問各個元素，因此適用于數(shù)組，不適用于鏈表。
• 歸并排序，需要將整個數(shù)組（鏈表）分成兩部分分別歸并：在比較的過程中只比較相鄰的兩個元素大小；在合并的過程中需要順序訪問數(shù)組（鏈表）。因此不需要隨機訪問元素，是適用于這里的場景的。

下面我們來看代碼。

代碼如下

Java版

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: You should return the head of the sorted linked list,
                    using constant space complexity.
     */
    public ListNode sortList(ListNode head) {  
        // write your code here
        return mergeSort(head);
    }
    
    private ListNode mergeSort(ListNode head) {
        if(null == head || null == head.next)
            return head;
            
        ListNode fast = head, slow = head, prevSlow = slow;
        while(fast != null && fast.next != null) {
            prevSlow = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        prevSlow.next = null;
        ListNode head2 = slow;
        head = mergeSort(head);
        head2 = mergeSort(head2);
        return merge(head, head2);
    }
    
    private ListNode merge(ListNode head1, ListNode head2) {
        if(null == head1)
            return head2;
        if(null == head2)
            return head1;
        ListNode head = new ListNode(0), p = head;
        while(head1 != null && head2 != null) {
            if(head1.val < head2.val) {
                p.next = head1;
                head1 = head1.next;
                p = p.next;
            } else {
                p.next = head2;
                head2 = head2.next;
                p = p.next;
            }
        }
        if(head1 != null)
            p.next = head1;
        if(head2 != null)
            p.next = head2;
        return head.next;
    }
}

關注我
該公眾號會每天推送常見面試題，包括解題思路是代碼，希望對找工作的同學有所幫助

image