创建一单向链表,并使用复杂度为O(nlg(n))的排序算法对该单向链表进行由小到大排序。

占个地TvT... 我想说这个10分总归有点太便宜了TvT....

我先琢磨去|||

写注释去...

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

struct s_node
{
int i;

s_node *next;
};

s_node * create_list(int in_n)
{
s_node *head = 0, *p;

head = new s_node;

head->i = rand();

p = head;

for (int i = 1; i < in_n; i++)
{
s_node *n = new s_node;

n->i = rand();

p->next = n;
p = n;
}

return head;
}

s_node _end_node = {0x7FFFFFFF}; // 用来标记排序时子链表的结尾

s_node * sort_list(s_node **in_list, int in_n) // 对给定链表的前n个节点排序，返回第n+1个节点
{
if (in_n == 2) // 链表有两个元素的时候，判断是否交换顺序，并截断
{
s_node *a = *in_list;
s_node *b = a->next;
s_node *r = b->next;

if (a->i > b->i)
{
*in_list = b;
b->next = a;
a-