1 struct node *create(int n)//顺序建立链表   2 {   3     int i,num;   4     struct node *head,*tail,*p;   5     head = (struct node*)malloc(sizeof(struct node));   6     head -> next = NULL;   7     tail = head;   8     for(i = 0;i < n;i ++)   9     {  10         scanf("%d",&num);  11         p = (struct node*)malloc(sizeof(struct node));  12         p -> data = num;  13         p -> next = NULL;  14         tail -> next = p;  15         tail = p;  16     }  17     return head;  18 }  19 struct node *create(int n)  //逆序20 {  21     struct node *head,*tail,*p;  22     int i,num;  23     head = (struct node*)malloc(sizeof(struct node));  24     head -> next = NULL;  25     tail = NULL;  26     for(i = 0;i < n;i ++)  27     {  28         scanf("%d",&num);  29         p = (struct node*)malloc(sizeof(struct node));  30         p -> data = num;  31         p -> next = tail;  32         tail = p;  33     }  34     head -> next = tail;  35     return head;  36 }  37 struct node *reverse(struct node *head)//反转38 {39     struct node *s,*p,*tail;40     s = head -> next;41     tail = NULL;42     while(s)43     {44         p = s -> next;45         s -> next = tail;46         tail = s;47         s = p;48     }49     head -> next = tail;50     return head;51 }52 void show(struct node *head)//显示53 {54     int flag = 1;55     struct node *s;56     s = head -> next;57     while(s)58     {59         if(flag) flag = 0;60         else printf(" ");61         printf("%d",s->data);62         s = s -> next;63     }64 }

 归并排序 链表版本 写了一个晚上。。

1 #include 
     
       2 #include 
      
        3 struct node 4 { 5     int data; 6     struct node *next; 7 }; 8 struct node *create(int n) 9 {10     int i,num;11     struct node *head,*tail,*p;12     head = (struct node *)malloc(sizeof(struct node));13     head -> next = NULL;14     tail = head;15     for(i = 0;i < n;i ++)16     {17         scanf("%d",&num);18         p = (struct node *)malloc(sizeof(struct node));19         p -> data = num;20         p -> next = NULL;21         tail -> next = p;22         tail = p;23     }24     return head;25 }26 struct node *merge(struct node *s1,struct node *s2)27 {28     struct node *head,*tail;29     head = (struct node *)malloc(sizeof(struct node));30     head -> next = NULL;31     tail = head;32     while(s1&&s2)33     {34         if(s1->data > s2->data)35         {36             tail -> next = s1;37             tail = s1;38             s1 = s1 -> next;39         }40         else41         {42             tail -> next = s2;43             tail = s2;44             s2 = s2 -> next;45         }46     }47     if(s1)48     tail -> next = s1;49     else50     tail -> next = s2;51     return head -> next;52 }53 void show(struct node *head)54 {55     struct node *s;56     int flag = 1;57     s = head ;//-> next;58     while(s)59     {60         if(flag) flag = 0;61         else printf(" ");62         printf("%d",s -> data);63         s = s -> next;64     }65     printf("\n");66 }67 struct node *sort(struct node *head)68 {69     struct node *s1,*s2,*p,*q;70     s1 = head;71     if(s1 -> next == NULL)72     return s1;73     s2 = s1 -> next;74     while(s2 -> next)75     {76         s1 = s1->next;77         s2 = s2->next;78         if(s2 -> next == NULL) break;79         s2 = s2->next;80         if(s2 -> next == NULL) break;81     }82     p = s1 -> next;83     s1 -> next = NULL;84     q = merge(sort(head),sort(p));85     return q;86 }87 88 89 int main()90 {91     int n;92     struct node *head;93     scanf("%d",&n);94     head = create(n);95     head = sort(head->next);96     show(head);97     return 0;98 }