Description
- Sort a linked list using insertion sort.
- Sort a linked list in O(n log n) time using constant space complexity.
这里顺便作为链表排序的总结吧,后期把遇到的链表排序问题都放过来
Solution
这里给出链表的插入排序(leetcode147),链表的快速排序,归并排序(leetcode148)
插入排序
插入排序没什么好说的,按照数组的插入排序的思想,甚至不用算法导论上给出的经典方法,因为链表不用移位。
快速排序
数组的快速排序的思想就是在数组中选择一个元素(一般是边界元素),将小于该元素的作为一个子数组,将剩下的元素作为另一个子数组,重复该过程,最后将这两个子数组合并返回。时间复杂度的均值是nlgn,空间复杂度在链表这没优势。
这里在leetcode中没有通过(14/15),原因是快排对于有序链表,用上面的思想时间复杂度是O(n^2),而最后一个test就是有序的…
归并排序
原理就是将一个数组等分为两个子数组,继续上述过程,最后合并这两个子数组;和快排差不多,但是对于数组而言,需要开辟O(n)的空间,但是链表就没有了,很适合链表。