学步园

好题目，总结一下。

要求时间效率O(NlogN)，空间限制为O(1)

1、暴力显然不行，于是想到那几种排序，堆排，快排，归并。堆排空间O(N)，pass；快排，给出的ListNode结构没有parent指针，pass；

2、归并，觉得也是空间O(N)，绝望。后来看了看别人的解法，顿觉自己还是too naive。既然已经是链表了，merge的时候把对位的连到后边不就行，怎么会蠢到想去一个个复制那些节点。

3、由于是链表，没有下标，计算mid位置的时候有一个小trick：快慢指针。快指针一次走两步，慢指针一次走一步。快指针走到链表末尾的时候，慢指针正好走到mid位置。（如果要求走到1/4位置呢？快4慢1）。

#include <iostream>
using namespace std;


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, *quick = head;
		ListNode *pre = slow;
		
		while(quick)
		{
			if(quick->next)
			{
				pre = slow;
				slow = slow->next;
				quick = quick->next;
				if(quick->next)
					quick = quick->next;
				else
					break;
			}
			else
				break;	
		}
		
		pre->next = 0;
		
		ListNode *l = sortList(head);
		ListNode *r = sortList(slow);
		return merge(l, r);
    }
    
    ListNode* merge(ListNode *l, ListNode *r)
    {
    	ListNode *head = new ListNode(0);
 		ListNode *p = head;
    	while(l && r)
		{
			if(l->val < r->val)
			{
				p->next = l;
				l = l->next;
			}
			else
			{
				p->next = r;
				r = r->next;	
			}
			p = p->next;			
		}
		if(l)
			p->next = l;
		else
			p->next = r;
			
		p = head->next;
		head->next = 0;
		delete head;
		
		return p;	
    }
    void insert(ListNode *head, int val)
    {
    	ListNode *p = new ListNode(val);
    	
    	if(!head)
    		return;
   		else
		{
			while(head->next)
			{
				head = head->next;
			}
			head->next = p;
		}
    }
    
    void print(ListNode *head)
    {
    	while(head->next)
    	{
    		head = head->next;
	    	cout << head->val << " ";	
	    }
	    cout << endl;
    }
};

int main(void)
{
	Solution s;
	ListNode head(0);
	for(int i = 9; i > 0; --i)
		s.insert(&head, i);
	s.print(&head);
	
	s.sortList(&head);
	s.print(&head);
	
	return 0;
}