怎么用C语言写单链表的排序

head指向链表的头节点，

从键盘输入不定数量的数字构造链表，输入0结束，然后排序输出，代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef struct _list {
int val;
struct _list* next;
} *node, list;


node Insert( node* head, node pos, int val )
{
node tmp;
tmp = ( node )malloc( sizeof( list ) );
tmp->val = val;
tmp->next = pos ? pos->next : *head;
if ( pos ) {
pos->next = tmp;
} else {
*head = tmp;
}
return tmp;
}


node Create( void )
{
node head, t;
int n;
head = t = NULL;
while ( scanf( "%d", &n ) && n != 0 ) {
t = Insert( &head, t, n );
}
return head;
}


void Print( node head )
{
while ( head ) {
printf( "%d ", head->val );
head = head->next;
}
putchar( '\n' );
}


node msort( node* head, int n )
{
int i, m;
node l, r, p, *x, *y;
if ( n < 2 ) return *head;
m = n/2;
p = l = r = *head;
for ( i = m; i > 0; --i )
p = r, r = r->next;
p->next = NULL;
l = msort( &l, m );
r = msort( &r, n - m );
x = &p;
while ( l && r ) {
*x = l->val < r->val ? (y = &l, l) : (y = &r, r);
*y = (*y)->next; x = &(*x)->next;
}
l = l ? l : r ? r : NULL;
*x = l; *head = p;
return p;
}


void Sort( node* head )
{
int i;
node tmp = *head;
for ( i = 0; tmp; ++i, tmp = tmp->next );
msort( head, i );
}


int main( void )
{
node head = Create();
Print( head );
Sort( &head );
Print( head );
getch();
return 0;
}


望采纳

#include"stdio.h" #include"stdlib.h" #define MAX 20 struct node { int num; struct node *next; }; typedef struct node node; void main() { int a[MAX]={4,3,3,7,4,8,1,2,2,7,6,7,9,12,15,0,-1,243,23,1}; int i; node *head,*p,*tail,*t; head=NULL; for (i=0;i<MAX;i++) { p=(node *)malloc(sizeof(node)); p->num=a[i]; p->next=NULL; if (head==NULL) head=t=p; else { t=head; while (t!=NULL) { if (p->num<t->num && t->next==NULL) { t->next=p; break; } else if (p->num>t->num && t!=head) { tail->next=p; p->next=t; break; } else if (p->num>t->num && t==head) { p->next=t; head=p; break; } tail=t; t=t->next; } } } while (head!=NULL) { printf("%d,",head->num); head=head->next; } printf("\n"); }