LeetCode148. Sort List（链表 / 模拟）

Medium
Accepted：170,901
Submissions：502,827

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

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

链接

https://leetcode.com/problems/sort-list

题意

对一个链表进行排序，要求时间复杂度为$O(nlogn)$，空间复杂度为常数。

题解

对链表排序是一件比较麻烦的事情，因为不支持随机访问。由于时间复杂度的限制，我们考虑下快速排序和归并排序，对于快速排序，每次都需要先找一个基准值然后左右两边递归排序操作起来非常麻烦。而归并排序只需要递归的将元素分成两半然后进行合并，操作起来比较简单。

同时又要求空间复杂度为常数，因此得使用非递归形式的归并排序。

代码

Runtime: 76 ms, faster than 29.31% of C++ online submissions for Sort List.
Memory Usage: 28.8 MB, less than 8.79% of C++ online submissions for Sort List.

// 递归形式
// 时间复杂度 O(nlogn)
// 空间复杂度 O(logn)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) // slow作为中间的结点
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* head2 = slow->next;
        slow->next = NULL;
        head = sortList(head);
        head2 = sortList(head2);
        return merge(head, head2);
    }

private:
    ListNode* merge(ListNode* a, ListNode* b)
    {
        ListNode* dummyHead = new ListNode(-1);
        ListNode* p1 = a;
        ListNode* p2 = b;
        ListNode* p = dummyHead;
        while (p1 && p2)
        {
            if (p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
            p->next = NULL;
        }
        if (p1)  // 剩余所有元素
            p->next = p1;
        if (p2)
            p->next = p2;

        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }
};

非递归形式，待填坑

The end.
2019年3月7日星期四