[Leetcode]148. Sort List(C++)

题目描述

题目链接：148. Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

例子

例子 1

Input: head = [4,2,1,3] Output: [1,2,3,4]

例子 2

Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5]

例子 3

Input: head = [] Output: []

Follow Up

Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Constraints

The number of nodes in the list is in the range [0, 5 * 10^4].

-10^5 <= Node.val <= 10^5

解题思路

题目要求在 O(nlogn) 的时间复杂度下对链表排序，不难想到可以使用归并排序，由于是链表所以可以自由控制节点的位置，无需使用额外空间。归并算法的思路是对链表首先分半，对前后两半递归使用排序，将排好序的链表合并在一起就行。合并排好序的链表很简单，可以参考：[Leetcode]21. Merge Two Sorted Lists(C++)

代码如下：

class Solution {
public:
    ListNode* sortList(ListNode* head) {

        // for linked list with length of 0 or 1, no need to sort
        if (!head || !head->next) {
            return head;
        }

        ListNode *dummy = new ListNode();
        dummy->next = head;

        ListNode *fast = dummy;
        ListNode *slow = dummy;

        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }

        fast = slow->next;
        slow->next = nullptr;

        return merge(sortList(head), sortList(fast));
    }

private:
    ListNode* merge(ListNode *A, ListNode *B) {
        ListNode *dummy = new ListNode();
        ListNode *curr = dummy;

        while (A && B) {
            if (A->val <= B->val) {
                curr->next = A;
                A = A->next;
            } else {
                curr->next = B;
                B = B->next;
            }
            curr = curr->next;
        }

        if (!A) {
            curr->next = B;
        }
        if (!B) {
            curr->next = A;
        }

        return dummy->next;
    }
};

时间复杂度: O(nlgn)
空间复杂度: O(1)

GitHub 代码同步地址： 148.SortList.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions