首页 > 代码库 > ［LeetCode蠕动系列］Sort List
［LeetCode蠕动系列］Sort List
这题前一阵子就看到了，一直没时间做，昨晚睡前想了想，要求n*log(n)以内的时间复杂度，第一时间想到的就是归并、快排和希尔排序（注：希尔排序时间为O(n^1.3)，在数据量大于2的情况下小于n*log(n)），个人以为，链表的特性更适合归并，所以采用归并排序，实现的merge代码如下：
public static ListNode merge(ListNode rhead, ListNode lhead) { ListNode head = null; if (rhead.val <= lhead.val) { head = rhead; rhead = rhead.next; } else { head = lhead; lhead = lhead.next; } ListNode node = head; while(rhead != null || lhead != null){ if (rhead == null) { node.next = lhead; lhead = lhead.next; } else if (lhead == null) { node.next = rhead; rhead = rhead.next; } else if (rhead.val <= lhead.val) { node.next = rhead; rhead = rhead.next; } else { node.next = lhead; lhead = lhead.next; } node = node.next; } return head; }while中开始写为
if (rhead == null ||rhead.val <= lhead.val)) {...}else(..) {...}报NullPoint异常，问题在于：|| 会判断每一个条件，如果rhead = null,那么rhead.val 错误；
然而这段代码在提交LeetCode时候报错：timeout, 修改while下代码：
while(rhead != null && lhead != null){ if (rhead.val > lhead.val) { node.next = lhead; lhead = lhead.next; } else if (lhead.val >= rhead.val) { node.next = rhead; rhead = rhead.next; } node = node.next; } if (rhead == null) { while(lhead != null) { node.next = lhead; lhead = lhead.next; node = node.next; } } else if (lhead == null) { while(rhead != null) { node.next = rhead; rhead = rhead.next; node = node.next; } }代码没有之前简洁，但是一下子就accepted.
但是对于这个问题一直耿耿于怀，然后google了下，给他跪了：time out is server‘s problem...
再次提交前面代码，果然通过AC……
但是对比下时间，后面的代码用时432ms,前面的代码用时476ms,除去每次运行的差异，个人认为，还一部分原因是：前面代码while每次都需要判断两个链表是否为null, 此处存在一定的时间开销，后面代码在一个链表为空以后，另一个链表只需不断迭代到为空。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。