148. Sort List

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

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

Thoughts

对链表排序要求O(1)空间。排序可用merge sort，heap sort或quick sort。quick sort由于需要swap在这里并不好用，heap需要O(N)额外空间，只有merge sort符合条件（如果不考虑调用栈的空间消耗）。merge sort用到了分治的思想，和处理二叉树类似，把input space分成左右两部分，递归调用自己。假设已经左右已经排好序了，再把left和right list合并。把递归树画出来，会是一棵高度为lgn的二叉树，每层一共有n个结点，从一个层往上一层回溯一共耗时n排序(这里还有耗时n找中间结点)，因此一共复杂度O(nlgn)。merge sort是稳定的。

Code

/*
 * @lc app=leetcode id=148 lang=cpp
 *
 * [148] Sort List
 */

// @lc code=start
/**
 * 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 == nullptr || head->next == nullptr) return head;
        const auto mid = [&]() {
            auto slow = head, fast = head->next;
            while (fast != nullptr && fast->next != nullptr) {
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        };
        auto slow = mid(), next = slow->next;
        auto r = sortList(slow->next);
        slow->next = nullptr;
        auto l = sortList(head);
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        while (l != nullptr || r != nullptr) {
            if (r == nullptr || l != nullptr && l->val <= r->val) {
                cur->next = l;
                l = l->next;
            } else if (l == nullptr || r != nullptr && r->val <= l->val) {
                cur->next = r;
                r = r->next;
            }
            cur = cur->next;
        }
        return dummy->next;
    }
};
// @lc code=end

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode mid = getMid(head);
        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);

        return merge(left, right);
    }

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

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0), node = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                node.next = left; 
                left = left.next;
            } else {
                node.next = right;
                right = right.next;
            }

            node = node.next;
        }
        if (left != null) {
            node.next = left; 
        } else {
            node.next = right;
        }

        return dummy.next;
    }


}

Analysis

注意切开操作: mid.next = null;

TC: O(nlgn)