单链表的快速排序_快速排序法有一个带头节点的整数单链表l,设计一个算法,将所有的负数节点移动到前

****【习题 2-13】设有一个带头结点的单链表 L，其中 data 为整数元素。设计一个算法， 首先按递减次序输出该单链表中各结点的数据元素，然后释放所有结点占用的存储空间，并 要求算法的空间复杂度为O(1)

一开始要对单链表排序，空间复杂度又为O（1），快一点的只能是快排和归并。

void swap(ElemType *a,ElemType *b)
{
	ElemType x=*a;
	*a=*b;
	*b=x;
}
node *GetPartion(node *begin,node *end)
{
	int key=begin->data;
	node *p=begin,*q=p->next;
	while(q!=end)
	{
		if(q->data<key)
		{
			p=p->next;
			swap(&p->data,&q->data);
		}
		q=q->next;
	}
	swap(&p->data,&begin->data);
	return p;
}
Status Quicksort(node *begin,node *end)
{
	if(begin==end)
		return ERROR;
	node *a=GetPartion(begin,end);
	Quicksort(begin,a);
	Quicksort(a->next,end);
	return OK;
}

#include<stdio.h>
#include<stdlib.h>
#define Status