147.c

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

structListNode {
intval;
structListNode*next;
};

structListNode*insertionSortList(structListNode*head) {
if (head==NULL) returnNULL;

structListNode*dummy= (structListNode*)malloc(sizeof(structListNode));
dummy->val=0;
dummy->next=NULL;
structListNode*t=dummy;

structListNode*p;
structListNode*min_ptr, *min_prev; /* prev node of min node */
intmin_val;
p=head;

while (p) {
min_val=p->val;
min_ptr=p;
min_prev=NULL;

structListNode*q=p->next;
structListNode*prev=p;
while (q) {
if (q->val<min_val) {
min_val=q->val;
min_prev=prev;
min_ptr=q;
 }
prev=q;
q=q->next;
 }

if (p==min_ptr) { /* if min node is p, we don't need to modify list */
p=p->next; /* just move forward p, and the min_prev is still */
 } /* NULL now. */
else {
min_prev->next=min_ptr->next; /* take node from list */
 }
t->next=min_ptr;
t=t->next;
 }
t->next=NULL;

t=dummy->next;
free(dummy);

returnt;
}

voidprint(structListNode*head) {
while (head) {
printf("%d ", head->val);
head=head->next;
 }
printf("NIL\n");
}

intmain() {
intn=10;
structListNode*head= (structListNode*)calloc(n, sizeof(structListNode));
structListNode**p=&head;
inti;

srand(time(NULL));
for (i=0; i<n; i++) {
 (*p)->val=rand() % n;
 (*p)->next=*p+1;
p=&((*p)->next);
 }
*p=NULL;

printf("List: ");
print(head);

structListNode*new_head=insertionSortList(head);

printf("Sorted: ");
print(new_head);

return0;
}