1.设有n 个整数组成的序列存放于一个带头结点的单链表中,HEAD为头指针.每个整数为－1,0,1之一.编写一个时间复杂度为O（n）的算法,使该序列按负数、零、正数的次序排好.(数据结构问题,用C解决)

//此题适用计数排序
#include
#include
typedef struct node
{
int num;
struct node * next;
}Node,*List;
List ListInit(List Head,int n)
{
List p;
int i;
for(i = 0; i {
p = (List)malloc(sizeof(Node));
p->next = Head;
Head = p;
}
return Head;
}
List ListReleas(List Head)
{
List p = Head;
while(Head)
{
p = Head;
Head=p->next;
free(p);
}
return Head;
}
int main()
{
List Head = NULL,p = NULL;
int count[3] = {0},n,inum;
printf("输入节点数：");
scanf("%d",&n);
Head = ListInit(Head,n);
printf("输入每个节点值（共%d个,只接受-1,0,1）：\n",n);
p = Head;
while( p != NULL )
{
scanf("%d",&p->num);
if(p->num num > -2)
p = p->next;
}
//以下为排序（计数排序）
p = Head;
while( p != NULL )
{
count[p->num + 1] ++;
p = p->next;
}
p = Head;
inum = -1;
while( p != NULL )
{
if(count[inum + 1])
{
p->num = inum;
p = p->next;
count[inum + 1]--;
}
else
inum ++;
}
//以下为输出
p = Head;
while( p != NULL )
{
printf("%d ",p->num);
p = p->next;
}
printf("\n");
ListReleas(Head);
return 0;
}