本文共 1560 字,大约阅读时间需要 5 分钟。
依然是一道我做不出来的题。。像这种题只有这次看题解看懂了下次再自己重做一次来巩固了。对我来说这道题好像有点超出我的范围了,不过经过一个小时的看题解的过程,,我终于是写出来了。。。惨。。
这道题不仅是归并排序,而且还规定了常数级空间。而我归并排序以前只是有模糊的记忆,直到今天才真正学了归并排序,而且,这里不能用递归,不然就不是常数级空间了。
首先,要理解的是什么是归并排序,就是这样的,假如有n个数,你第一次排序,把n个数分成n份,然后两份一组排序,两份一组排序,都排好了后现在就是n/2组,每一组都是排好序的,虽然后来,下一次就是分成n/2份,每份两个元素,再来两份一组两份一组的排序,知道最后只分成了1份,那么这个数组就是通过归并排序排好的了。思路应该很容易理解,只是代码的实现就不是这么容易了,因为这里是链表!不是数组。。。
cut声明为表示每份的元素个数,每一次大循环后cut的值变为原来的两倍。归并排序是每两份一组,每两份一组的进行排序的,知道链表为nil。所以首先声明h1,来表示第一组,声明i=cut,h1每向后next一下,i--,退出条件就是i<=0 || h1 == nil这里要注意的是假如此时退出来了而i是大于0的,那么就跳出这次循环,说明后面已经没有h2能够和他进行合并操作了。假如<=0,那么就继续选择出第二组,第二组就没有i的问题,就算i>0,照样可以进行归并排序。不过我们要声明一个变量v2=cut-i,来表示第二组的元素个数,因为有可能第二组并没有那么多元素。当这都准备好了后就可开始进行合并了,合并完成后将还不为nil的链表那组直接加在总链表的后面,当然,这个时候还要更新pre.next为当前h,因为这一组大循环还没有结束,下一次就是另外两组元素来进行了。最后我们返回res.next就是排好序的链表。
我确实觉得这道题的难度有点大了,假如面试的时候碰到这道题我也只有认了。。。
代码如下:
/**
* Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func sortList(head *ListNode) *ListNode { length,cut := 0,1 res := &ListNode{} res.Next = head h := head for h != nil { h = h.Next length++ }for cut < length {
pre := res h := res.Next for h != nil{ i := cut h1 := h for i > 0 && h != nil { i-- h = h.Next } if i >0 { break } i = cut h2 := h for i>0 && h != nil { i-- h = h.Next } v1,v2 := cut,cut-i for v1 >0 && v2 > 0 { if h1.Val < h2.Val { pre.Next = h1 h1 = h1.Next v1-- }else{ pre.Next = h2 h2 = h2.Next v2-- } pre = pre.Next } if v1==0 { pre.Next = h2 }else{ pre.Next = h1 } for v1 > 0 || v2 > 0 { pre = pre.Next v1-- v2-- } pre.Next = h } cut = cut * 2 } return res.Next}
java版:
还是感觉难。。。
转载地址:https://blog.csdn.net/qq_40058686/article/details/104426175 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!