Leetcode Sort List 链表归并排序

Sort List

Sort a linked list inO(nlogn) time using constant space complexity.

本题好像使用quicksort是不能AC的，只能使用归并排序了。

之前觉得是很困难的题目。

训练了这么久算法，功力终于上升了。虽然还没达化境，但是以前觉得什么归并排序，快速排序好像很难，曾经死记过，始终没有记住，一直都觉得很困惑，怎么才能写出这些算法出来。如今，随时都能写出这样算法来了。而且代码基本上都很工整，清晰的，O(∩_∩)O~

原来算法是练出来的，不是死记硬背的。

我说的化境，是觉得有一天会无论什么难题都可以轻松利用学过的算法，转化成优雅的代码，那时候所有算法都已经融会贯通了，所有题目差不多是一样的，所有算法也是差不多的。呵呵。

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	ListNode *sortList(ListNode *head) 
	{
		if (!head || !head->next) return head;

		ListNode *slow = head;
		ListNode *fast = head->next;

		while (fast->next)
		{
			slow = slow->next;
			fast = fast->next;
			if (fast->next) fast = fast->next;
		}
		ListNode *h2 = slow->next;
		slow->next = NULL;
		
		head = sortList(head);
		h2 = sortList(h2);
		head = combinTwoList(head, h2);
		return head;
	}

	ListNode *combinTwoList(ListNode *n1, ListNode *n2)
	{
		ListNode dummy(0);
		dummy.next = n1;
		ListNode *pre = &dummy;

		while (pre->next && n2)
		{
			if (pre->next->val > n2->val)
			{
				ListNode *t = n2->next;
				n2->next = pre->next;
				pre->next = n2;
				pre = n2;
				n2 = t;
			}
			else pre = pre->next;
		}
		if (n2) pre->next = n2;
		return dummy.next;
	}
};

//2014-2-19 update
	ListNode *sortList(ListNode *head) 
	{
		if (!head || !head->next) return head;
		ListNode *slow = head;
		ListNode *fast = head;
		while (fast->next && fast->next->next)
		{
			slow = slow->next;
			fast = fast->next->next;
		}
		fast = slow->next;
		slow->next = nullptr;
		head = sortList(head);
		fast = sortList(fast);
		return mergeList(head, fast);
	}
	ListNode *mergeList(ListNode *h1, ListNode *h2)
	{
		ListNode dummy(0);
		ListNode *p = &dummy;
		while (h1 && h2)
		{
			if (h1->val < h2->val)
			{
				p->next = h1;
				h1 = h1->next;
			}
			else
			{
				p->next = h2;
				h2 = h2->next;
			}
			p = p->next;
		}
		if (h1) p->next = h1;
		else p->next = h2;
		return dummy.next;
	}