求问老师leetcode 的148 题要怎么做到constant space complexity
来源：5-7 更多和链表相关的问题
慕前端6301706
2019-02-08
我的想法是merge sort 但是这样的话需要new 一个新的listnode 再进行merge的话应该space就超过了 不知道老师有没有什么提示
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
1回答
-
liuyubobobo
2019-02-09
new一个ListNode仍然是O(1)的时间复杂度：）
对于链表来说，如果给定两个有序链表，进行和并，是可以非常简单的用O(1)的空间搞定的。这是链表比数组方便的地方：）具体可以先尝试一下这个问题：https://leetcode.com/problems/merge-two-sorted-lists/
对链表进行归并排序，真正有些小技巧的，是进行”二分“的过程。但是最坏情况下，使用O(n)的时间进行遍历，了解整个链表有多少元素（假设为n），之后在遍历前n/2个元素，也能找到中间节点。
另一个方法是使用双指针。快慢两个指针。快指针每次挪动两步，慢指针每次挪动一步，最后，慢指针对应的位置就是中间位置：）
我在我的Leetcode解题代码仓中，实现了一个基于链表的归并排序，可以参考：）（C++源码）
https://github.com/liuyubobobo/Play-Leetcode/blob/master/0148-Sort-List/cpp-0148/main.cpp
加油！：）
022019-02-09
相似问题