单向链表排序

这里实现的复杂度是O(n^2)的，后续有时间不上更高效的。

实现的流程主要就是利用类似冒泡排序的思想，每一次遍历找出最小值的那个节点now，此时记录该节点的前一个节点指针prev（这里只要前一个就可以了，因为找到的这个可以用now = prev->next来获得，这样节省空间），然后使now掉链，把它挂载到已经排好序的节点的后面。然后重新循环找到无序链中的最小的节点。

typedef struct linknd_s {
        int data;
        struct linknd_s *next;
}linknd_t;

void create_link(linknd_t **head_t)
{
        int count = 0;
        linknd_t *head = *head_t;
        if (head == NULL) {
                head = malloc(sizeof(linknd_t));
                if (head == NULL) {
                        printf("error create link\n");
                        return;
                }

                scanf("%d", &head->data);
                head->next = NULL;
        }
        linknd_t *t = head;
        while (count != 9) {
                linknd_t *node = malloc(sizeof(linknd_t));
                if (node == NULL) {
                        printf("count = %d\n", count);
                        return;
                }
                printf("enter the linkdata:\n");
                scanf("%d", &node->data);
                t->next = node;
                node->next = NULL;
                t = node;
                count++;
        }
        *head_t = head;
        return;
}

void link_sort(linknd_t **head)
{
        linknd_t *tmp, *prev = NULL, *head_t = NULL;
        linknd_t start;

        if (*head == NULL)
                return;

        start.next = *head;
        head_t = &start;
        while(head_t && head_t->next) {
                tmp = head_t->next;
                prev = head_t;
                while(tmp->next) {
                        if (tmp->next->data < prev->next->data) {
                                prev = tmp;
                        }
                        tmp = tmp->next;
                }

                if (prev != head_t){
                        linknd_t *s = prev->next;
                        prev->next = s->next;
                        s->next = head_t->next;
                        head_t->next = s;

                }
                head_t = head_t->next;
        }

        *head = start.next;
        return;
}


int main(void)
{
        printf("create the link list\n");
        linknd_t *head = NULL, *tmp;
        create_link(&head);
        tmp = head;

        while (head) {
                printf("%d\n", head->data);
                head = head->next;
        }

        link_sort(&tmp);

        while (tmp) {
                printf("%d\n", tmp->data);
                tmp = tmp->next;
        }
        return 0;
}