LeetCode Sort List

148. Sort List

Sort a linked list in O(n log 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

本题要求用O(nlogn)的时间复杂度和常数空间复杂度对一个链表排序。 O(nlgn)的排序算法有快速排序、堆排序、归并排序,快排和堆排都需要对元素的随机访问,不适用于链表,这里我们可以用归并排序实现。 归并的思路是不断把链表对分成两个子链表,直到只剩一个节点,此时一个节点是有序的,然后不断的两两归并,mergeList就好办多了。 完整代码如下:

class Solution {
private:
    ListNode* mergeList(ListNode* h1, ListNode* h2)
    {
        if (!h1)
            return h2;
        else if (!h2)
            return h1;
        ListNode *head = new ListNode(0), *h = head;
        while (h1 && h2) {
            if (h1->val < h2->val) {
                h->next = h1;
                h1 = h1->next;
            }
            else {
                h->next = h2;
                h2 = h2->next;
            }
            h = h->next;
        }
        if (h1)
            h->next = h1;
        else if (h2)
            h->next = h2;
        return head->next;
    }
public:
    ListNode* sortList(ListNode* head)
    {
        if (!head || !head->next)
            return head;
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = NULL;
        ListNode* left = sortList(head);
        ListNode* right = sortList(fast);
        return mergeList(left, right);
    }
};

本代码提交AC,用时56MS。

二刷,归并排序还可以写得简单点:

class Solution {
public:
	ListNode* sortList(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *slow = head, *fast = head, *pre = head;
		while (fast != NULL && fast->next != NULL) {
			pre = slow;
			slow = slow->next;
			fast = fast->next->next;
		}
		pre->next = NULL;
		ListNode *left = sortList(head), *right = sortList(slow);
		ListNode *dummy = new ListNode(0);
		ListNode *lst = dummy;
		while (left != NULL || right != NULL) {
			int l = left != NULL ? left->val : INT_MAX;
			int r = right != NULL ? right->val : INT_MAX;
			if (l < r) {
				lst->next = left;
				left = left->next;
			}
			else {
				lst->next = right;
				right = right->next;
			}
			lst = lst->next;
		}
		return dummy->next;
	}
};

本代码提交AC,用时44MS。

Leave a Reply

Your email address will not be published. Required fields are marked *