【LeetCode——排序链表】

排序链表

一道链表排序题，链接在这里

二、解题思路：

解题思路：使用归并排序（用递归实现）

第一步：先找到链表的中间节点

第二步：将链表从中间节点开始断开

找到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);
}

总结：

使用归并排序是解题的较好的方法。