#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct Node
{
int value;
struct Node *next;
};
typedef struct Node Node;
Node* sortList(Node* head)
{
Node* newHead = NULL;
while (head)
{
Node **pp = &newHead, *tmp = head->next;
while (*pp && (*pp)->value < head->value)
pp = &(*pp)->next;
head->next = *pp;
*pp = head;
head = tmp;
}
return newHead;
}
void printList(const Node* head)
{
while (head)
{
head = head->next;
}
}
void freeList(Node *head)
{
while (head)
{
void *victim = head;
head = head->next;
}
}
int main()
{
Node* head = NULL, *tmp;
for (int i=0; i<20; ++i)
{
tmp
->value
= rand() % 100; tmp->next = head;
head = tmp;
}
printList(head);
head = sortList(head);
printList(head);
freeList(head);
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHRpbWUuaD4KCnN0cnVjdCBOb2RlCnsKICAgIGludCB2YWx1ZTsKICAgIHN0cnVjdCBOb2RlICpuZXh0Owp9OwoKdHlwZWRlZiBzdHJ1Y3QgTm9kZSBOb2RlOwoKCk5vZGUqIHNvcnRMaXN0KE5vZGUqIGhlYWQpCnsKICAgIE5vZGUqIG5ld0hlYWQgPSBOVUxMOwogICAgCiAgICB3aGlsZSAoaGVhZCkKICAgIHsKICAgICAgICBOb2RlICoqcHAgPSAmbmV3SGVhZCwgKnRtcCA9IGhlYWQtPm5leHQ7CiAgICAgICAgd2hpbGUgKCpwcCAmJiAoKnBwKS0+dmFsdWUgPCBoZWFkLT52YWx1ZSkKICAgICAgICAgICAgcHAgPSAmKCpwcCktPm5leHQ7CiAgICAgICAgCiAgICAgICAgaGVhZC0+bmV4dCA9ICpwcDsKICAgICAgICAqcHAgPSBoZWFkOwogICAgICAgIGhlYWQgPSB0bXA7CiAgICB9CiAgICAKICAgIHJldHVybiBuZXdIZWFkOwp9CgoKdm9pZCBwcmludExpc3QoY29uc3QgTm9kZSogaGVhZCkKewogICAgd2hpbGUgKGhlYWQpCiAgICB7CiAgICAgICAgcHJpbnRmKCIlZCAiLCBoZWFkLT52YWx1ZSk7CiAgICAgICAgaGVhZCA9IGhlYWQtPm5leHQ7CiAgICB9CiAgICBmcHV0YygnXG4nLCBzdGRvdXQpOwp9Cgp2b2lkIGZyZWVMaXN0KE5vZGUgKmhlYWQpCnsKICAgIHdoaWxlIChoZWFkKQogICAgewogICAgICAgIHZvaWQgKnZpY3RpbSA9IGhlYWQ7CiAgICAgICAgaGVhZCA9IGhlYWQtPm5leHQ7CiAgICAgICAgZnJlZSh2aWN0aW0pOwogICAgfQp9CgoKaW50IG1haW4oKQp7CiAgICBOb2RlKiBoZWFkID0gTlVMTCwgKnRtcDsKICAgIAogICAgc3JhbmQoKHVuc2lnbmVkKXRpbWUoTlVMTCkpOwogICAgCiAgICBmb3IgKGludCBpPTA7IGk8MjA7ICsraSkKICAgIHsKICAgICAgICB0bXAgPSBtYWxsb2Moc2l6ZW9mICp0bXApOwogICAgICAgIHRtcC0+dmFsdWUgPSByYW5kKCkgJSAxMDA7CiAgICAgICAgdG1wLT5uZXh0ID0gaGVhZDsKICAgICAgICBoZWFkID0gdG1wOwogICAgfQogICAgCiAgICBwcmludExpc3QoaGVhZCk7CiAgICBoZWFkID0gc29ydExpc3QoaGVhZCk7CiAgICBwcmludExpc3QoaGVhZCk7CiAgICBmcmVlTGlzdChoZWFkKTsKfQ==