排序链表
二、解题思路：
解题思路：使用归并排序（用递归实现）
第一步：先找到链表的中间节点
第二步：将链表从中间节点开始断开
找到mid节点(中间节点)的前一个节点，将两个链表断开。
第三步：重复上述操作，再在新链表中找中间节点，再分开，直到分开到链表剩下一个节点为止。
第四步，合并链表。
举个例子：
给两个链表：一个是1->2->3->4，一个链表是0->2->3->5
将这两个有序链表合并成一个有序链表。
网络异常，图片无法展示
|
申请一个哨兵位的头节点，不存储有效数据，然后使用l1,l2来遍历两个链表，比较l1和l2存储的值的大小。
回到上面的题，两个节点之间两两比较，只要满足升序要求即可。
合并俩节点后，再合并两个链表。
网络异常，图片无法展示
|
总效果如下图：
二.实现的代码
```c typedef struct ListNode ListNode; ListNode*midNode(ListNode*head) { ListNode*fast = head,*slow = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } //合并链表 ListNode*mergelist(ListNode*head1,ListNode*head2) { ListNode*newhead = (ListNode*)malloc(sizeof(ListNode)); ListNode*l1 = head1,*l2 = head2,*tail = newhead; while(l1 && l2) { if(l1->val <= l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } if(l1!=NULL) { tail->next = l1; } if(l2!=NULL) { tail->next = l2; } ListNode*ret = newhead->next; free(newhead); return ret; } ListNode*tosortList(ListNode*head) { //空链表和只有一个节点不用再排序了 if(head==NULL ||head->next == NULL) { return head; } //找中间节点 ListNode*mid = midNode(head); //找中间节点的前一个节点 ListNode*prev = head; while(prev->next!=mid) { prev = prev->next; } //断开链表 prev->next = NULL; //返回排序后的新链表的头 ListNode*left = tosortList(head); ListNode*right = tosortList(mid); return mergelist(left,right); } struct ListNode* sortList(struct ListNode* head) { return tosortList(head); }
总结：
使用归并排序是解题的较好的方法。
