[LeetCode]Sort List

Linkedlist的sort用merge sort，因为很容易可以发现quick sort的实现是很不方便的，因为我们需要从尾巴想头结点移动来进行partition。其次是Linkedlist的merge sort是constant space，没有比merge sort更适合sort链表的了。基本的思路还是如下:

• partition，分解成前半段和后半段两个节点
• 递归地分别sort两半linkedlist
• 归并，双指针merge成一个sorted的linkedlist

注意第一步partition的时候check的condition是fast->next != nullptr && fast->next->next != nullptr，这样可以保证我们在长度只有2的case当中仍然可以正确地partition。时间复杂度O(N * log N)，常数空间，代码如下：

	/**
	* 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) {
	return mergeSort(head);
	}
	private:
	ListNode* mergeSort(ListNode* head)
	{
	if(!head || !head->next)return head;
	//partition
	auto fast = head, slow = head;
	while(fast->next && fast->next->next)
	{
	fast = fast->next->next;
	slow = slow->next;
	}
	auto head2 = slow->next;
	slow->next = nullptr;
	auto curr1 = mergeSort(head), curr2 = mergeSort(head2);
	//merge
	ListNode* newHead = curr1->val <= curr2->val? curr1: curr2, *curr = newHead;
	if(curr == curr1)curr1 = curr1->next;
	else curr2 = curr2->next;
	while(curr1 && curr2)
	{
	if(curr1->val <= curr2->val)
	{
	curr->next = curr1;
	curr = curr->next;
	curr1 = curr1->next;
	}
	else
	{
	curr->next = curr2;
	curr = curr->next;
	curr2 = curr2->next;
	}
	}
	if(curr1)curr->next = curr1;
	if(curr2)curr->next = curr2;
	return newHead;
	}
	};

view raw Sort List.cpp hosted with ❤ by GitHub