[leetcode]链表排序

（一）题目描述 

 

 

（二）思想方法：

关于排序的方法有很多，但是符合O(nlogn)并适合链表的只有合并排序。

归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。归并排序算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))，算法不是自适应的，不需要对数据的随机读取。

（三）算法实现

ListNode* sortList(ListNode* head) { if (!head || !head->next) return head; ListNode *slow = head, *fast = head, *pre = head; while (fast && fast->next) { pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = NULL; return merge(sortList(head), sortList(slow)); } ListNode* merge(ListNode* l1, ListNode* l2) { ListNode *dummy = new ListNode(-1); ListNode *cur = dummy; while (l1 && l2) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } if (l1) cur->next = l1; if (l2) cur->next = l2; return dummy->next; }