Tag name:Linked List

[LeetCode] Sort List

01/30/2014 / 4 Comments

这个在LeetCode上有两题,一题要求用insertion sort,一提要求用O(nlogn)的方法
做insertion sort的时候脑子进水想成了selection sort,虽然写的没bug,但输入稍微大点的时候OJ说Time Limit Exceeded. 但按理selection sort和 insertion sort都是n^2的,咋会超时呢,先贴代码上来吧,想不通
最蛋疼的就是single linked list, 拿删除来说,你要删除当前节点是没办法做到的,你只能删除当前节点的next节点。所以每次都要去检查cur->next这个节点,若需要删除再把cur->next->next赋值给cur->next。
3/10 更新:忘记来更新这个了,插入排序前几周写好了,具体的话必须把list分成排序和未排序的两段,最开始的时候没有注意将第一段的末尾元素next置空导致cyclic蛋疼的好久