单链表快速排序_带头结点的单链表可以快速排序吗？

2015.11.27  面试一点资讯 ，面试官是很nice的校友师兄，无奈基本功太差，跪了！

#include <iostream>
 
using namespace std;
 
#define random(x) (rand()%x)
 
struct ListNode
{
	int value;
	ListNode* next;
};
 
void create_list(ListNode* head)
{
	ListNode* pNode = head;
	for(int i = 0; i < 10; i++)
	{
		ListNode* pNew = new ListNode;
		pNew->value = random(10);
		pNew->next = NULL;
 
		pNode->next = pNew;
		pNode = pNode->next;
	}
}
 
void print_list(ListNode* head)
{
	ListNode* pNode = head->next;
	while(pNode != NULL)
	{
		cout << pNode->value << ' ';
		pNode = pNode->next;
	}
	cout << endl;
}
 
void quick_sort(ListNode* head, ListNode* tail)
{
	if(head->next == tail || head->next->next == tail)
		return;
 
	ListNode* mid = head->next;
	ListNode* pLess = head;
	ListNode* pGreater = mid;
	int pivot = mid->value;
 
	ListNode* pNode = mid->next;
 
	while(pNode != tail)
	{
		if(pNode->value < pivot)
		{
			pLess->next = pNode;
			pLess = pNode;
		}
		else
		{
			pGreater->next = pNode;
			pGreater = pNode;
		}
 
		pNode = pNode->next;
	}
 
	pLess->next = mid;
	pGreater->next = tail;
 
	quick_sort(head, mid);
	quick_sort(mid, tail);
}
 
 
int main()
{
	ListNode* head = new ListNode;
	head->value = -1;
	head->next = NULL;
	
	create_list(head);
	print_list(head);
	quick_sort(head, NULL);
	print_list(head);
 
	return 0;
}