在 O(n log n) 时间复杂度和常数级空间复杂度下, 对链表进行排序.
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
此问题思路使用归并排序, 先贴上归并排序 go 语言解法:
- func merge(arrl []int,arrr []int) []int {
- fmt.Println("merge arr",arrl,arrr)
- i,j := 0,0
- tmp := make([]int,0)
- for i<len(arrl) && j<len(arrr){
- if (arrl[i]>arrr[j]){
- tmp = append(tmp,arrr[j])
- j++
- }else{
- tmp = append(tmp,arrl[i])
- i++
- }
- }
- tmp = append(tmp,arrl[i:]...)
- tmp = append(tmp,arrr[j:]...)
- return tmp
- }
- func MergeSort(arr []int) []int{
- l := len(arr)
- if (l<2){
- return arr
- }
- key := l/2
- fmt.Println("before left")
- left := MergeSort(arr[0:key])
- fmt.Println("after left",left)
- right := MergeSort(arr[key:])
- fmt.Println("after right",right)
- return merge(left,right)
- }
如果是链表的话, 思路不变, 做一些处理, 先去吃个东西. 稍后更新
来源: http://www.bubuko.com/infodetail-3275806.html