Linkedlist的sort用merge sort，因为很容易可以发现quick sort的实现是很不方便的，因为我们需要从尾巴想头结点移动来进行partition。其次是Linkedlist的merge sort是constant space，没有比merge sort更适合sort链表的了。基本的思路还是如下:
- partition，分解成前半段和后半段两个节点
- 递归地分别sort两半linkedlist
- 归并，双指针merge成一个sorted的linkedlist
注意第一步partition的时候check的condition是fast->next != nullptr && fast->next->next != nullptr，这样可以保证我们在长度只有2的case当中仍然可以正确地partition。时间复杂度O(N * log N)，常数空间，代码如下：
No comments:
Post a Comment