148.排序链表

148.排序链表题目描述：给出一个长度为 n 链表的头结点head，按照升序排列，并且返回排序之后的链表。数据范围： 0\le n \le 5 \times 10^4 题解：首先观察数据范围，发现只能使用 O(n\log(n)) 的算法解决。可供选择的有快排，堆排，归并。链表比较适合使用归并排序。与一般归并不同的是，需要合并成一个新的链表，注意需要返回头指针。一般的数组排序是需要将合并后的数据拷贝回原来的数组的，因此只需要记录每段的起点终点即可。因为链表的合并，最后返回了一个新的头指针，并且没有拷回。需要在分治与合并的都返回头指针。找中点可以使用快慢指针。合并时剩余的部分可以直接接到链表的尾部，不用一个一个遍历。代码：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263class Solution{public: ListNode *merge_sort(ListNode *head, ListNod...

Submit