单链表的归并排序(C语言)

//数据域val,指针域nextstruct ListNode{int val;struct ListNode* next;};

//创建单链表struct ListNode* CreatList(){struct ListNode* p1,* p2,* head;head=NULL;p1=p2=(struct ListNode*)malloc(sizeof(struct ListNode));printf("请输入整数(输入0结束输入):\n");scanf("%d",&p1->val);int n=0;while(p1->val != 0){++n;if(n==1){head=p1;}else{p2->next=p1;}p2=p1;p1=(struct ListNode*)malloc(sizeof(struct ListNode));scanf("%d",&p1->val);}p2->next=NULL;return head;}

//mergeTwoList() 升序合并两个链表struct ListNode* mergeTwoList(struct ListNode* head1,struct ListNode* head2){struct ListNode* p1,*p2,*p3;p1=head1,p2=head2;struct ListNode* newHead=(struct ListNode*)malloc(sizeof(struct ListNode));p3=newHead;while(p1 && p2){if(p1->val < p2->val){p3->next=p1;p3=p1;p1=p1->next;}else{p3->next=p2;p3=p2;p2=p2->next;}}p3->next=p1?p1:p2;return newHead->next;}//链表的归并排序struct ListNode* mergeSort(struct ListNode* head,struct ListNode* tail){if(head==NULL){return NULL;}if(head->next==tail){head->next=NULL;return head;}//利用快慢指针找到链表的中间结点struct ListNode* fast,* slow;fast=slow=head;while(fast != NULL){fast=fast->next;slow=slow->next;if(fast != NULL){fast=fast->next;}}struct ListNode* mid=slow;return mergeTwoList(mergeSort(head,mid),mergeSort(mid,tail));}struct ListNode* sort(struct ListNode* head){return mergeTwoList(head,NULL);}

int main(){struct ListNode* head;head=CreatList();printf("链表为:\n");Print(head);printf("\n排序后的链表为:\n");struct ListNode* list;list=sort(head);Print(list);}

运行结果为:

来源于LeetCode 148.排序链表~