148. Sort List
Merge sort:
- if head or head.next is none, return head.
- split the list from middle into A and B
- recursively merge sort A and B
- merge sorted A and sorted B
Complexity:
- time: Nlog(N)
- space: recursion call is at most log(N) deep, hence log(N)
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
1 | Input: 4->2->1->3 |
Example 2:
1 | Input: -1->5->3->4->0 |
Soulution:
1 | class Solution(object): |