利用快速排序对单链表进行排序

今天上午在K一道单链表排序题（目前LeetCode第四题），利用快速排序实现的版本过不了时间限制，不排除我实现中优化做得不够。Partition的算法和我在这篇blogC++实现的快速排序中使用的算法是类似的，都是参考自算法导论。虽然提交LeetCode的题目超时了，但是这个代码可以留作参考。至于题目，一会儿我用归并试试。

#include<iostream>
#include<ctime>
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 == NULL)
			return head;

		ListNode* tail=head;
		ListNode* end = tail;
		while (tail->next != NULL) { 
			//if (tail->next->next == NULL)
			//	end = tail;
			tail = tail->next; 

		}
		qSortList(head, tail);
		return head;
	}
	ListNode* Partition(ListNode* head, ListNode* tail)
	{

		ListNode* newHead = new ListNode(0);
		newHead->next = head;
		ListNode* ipt = newHead, *jpt = head;
		int ar = tail->val;
		while (jpt != tail)
		{
			if (jpt->val < ar)
			{
				ipt = ipt->next;
				swap(ipt->val, jpt->val);
			}
			jpt = jpt->next;
		}
		ipt = ipt->next;
		swap(ipt->val, tail->val);
		return ipt;
	}
	void qSortList(ListNode*head, ListNode*tail)
	{

		if (head == NULL)
			return;
		if (tail == NULL)
			return;
		if (tail->next!=NULL && tail->next == head)
			return;
		else if (tail->next!=NULL &&tail->next->next!=NULL &&  tail->next->next== head)
			return;
		
		if (head == tail)
			return;
		if (head->next == tail)
		{
			if (head->val > tail->val)
				swap(head->val,tail->val);
			return;
		}

		ListNode* mid = Partition(head, tail);
		ListNode*tail1 = head;
		if (tail1!=mid)
			while (tail1->next != mid) tail1 = tail1->next;
		ListNode*head2 = mid->next;
		qSortList(head, tail1);
		qSortList(head2, tail);
	}
};
int main()
{
	ListNode* head0 = new ListNode(200);
	ListNode* head = head0;
	srand(time(NULL));
	for (int i = 0; i < 10000; i++)
	{
		
		ListNode* mNode = new ListNode(rand() % 4);
		head0->next = mNode;
		head0 = head0->next;

	}
	Solution sln;
	ListNode*res=sln.sortList(head);
	while (res->next != NULL)
	{
		cout << res->val << " ";
		res = res->next;
	}
	return 0;
}