148.c

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

structListNode {
intval;
structListNode*next;
};

structListNode*merge(structListNode*left, structListNode*right) {
if (left==NULL) returnright;
if (right==NULL) returnleft;

structListNode*ans=NULL;
structListNode**p=&ans;

while (left&&right) {
if (left->val <= right->val) {
*p=left;
p=&((*p)->next);
left=left->next;
 }
else {
*p=right;
p=&((*p)->next);
right=right->next;
 }
 }

if (left) {
*p=left;
 }
elseif (right) {
*p=right;
 }

returnans;
}

structListNode*sortList(structListNode*head) {
if (head==NULL) returnNULL;
if (head->next==NULL) returnhead;

structListNode*p=head;
intlen=0;
while (p) {
len++;
p=p->next;
 }

structListNode*mid=head;
structListNode*prev=NULL;
inti=len / 2;
while (i--) {
prev=mid;
mid=mid->next;
 }
prev->next=NULL;

structListNode*left=sortList(head);
structListNode*right=sortList(mid);

returnmerge(left, right);
}

intmain() {
structListNode*head= (structListNode*)calloc(5, sizeof(structListNode));
structListNode**p=&head;
inti;
for (i=0; i<5; i++) {
 (*p)->val=5-i;
 (*p)->next=*p+1;
p=&((*p)->next);
 }
*p=NULL;

printf("List: ");
structListNode*q=head;
while (q!=NULL) {
printf("%d->", q->val);
q=q->next;
 }
printf("N\n");

structListNode*ret=sortList(head);

printf("Sort result: ");
q=ret;
while (q!=NULL) {
printf("%d->", q->val);
q=q->next;
 }
printf("N\n");

return0;
}