Sort List

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);
• 基数排序、计数排序，时间复杂度都是O(n)。

那么，这里的算法对于数组都适用，但对于单向链表不一定适用。在该题中要求时间复杂度为O(nlogn)，因此我们可以从快速排序、归并排序、堆排序中选择，看看有没有一种适合这里的情况。

• 快速排序，快排需要一个指针从前往后，另一个指针从后向前，但是这里用的是单向链表，无法快速的从后向前遍历，因此快速排序不适用这里的场景。
• 堆排序， 堆排序在排序的过程中需要比较第i个元素和第2 * i + 1个元素的大小，需要随机访问各个元素，因此适用于数组，不适用于链表。
• 归并排序，需要将整个数组（链表）分成两部分分别归并：在比较的过程中只比较相邻的两个元素大小；在合并的过程中需要顺序访问数组（链表）。因此不需要随机访问元素，是适用于这里的场景的。

下面我们来看代码。

代码如下

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;
    }
}