LeetCode Sort List

LeetCode Sort List

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


本题要求用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。

Leave a Reply

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