Middle-タイトル97:148.Sort List
3185 ワード
Sort a linked list in O(n log n)time using constant space complexity.タイトルの大意:1つの単鎖の表に対して並べ替えて、時間の複雑度O(nlogn)、空間の複雑度O(1)テーマの分析を要求します:discussの中のアルゴリズムを参考にして、速い列を使って、pivotを第1のノードの値に取ります.ソース:(language:java)
成績:8 ms,beats 42.09%,衆数8 ms,31.36%cmershenの砕けた念:配列の速い列の中でpivotは三者取中法を使用しているが,チェーンテーブルはランダムアクセスではなく,三者取中法を使用するにはチェーンテーブルを遍歴しなければならないが,かえって加速できない.
public class Solution {
public ListNode sortList(ListNode h){
if(h == null || h.next == null)
return h;
/*split into three list*/
ListNode fakesmall = new ListNode(0), small = fakesmall;
ListNode fakelarge = new ListNode(0), large = fakelarge;
ListNode fakeequal = new ListNode(0), equal = fakeequal;
ListNode cur = h; // pivot is h.
while(cur != null){
if(cur.val < h.val){
small.next = cur;
small = small.next;
}
else if(cur.val == h.val){
equal.next = cur;
equal = equal.next;
}
else{
large.next = cur;
large = large.next;
}
cur = cur.next;
}
// put an end.
small.next = equal.next = large.next = null;
// merge them and return . merge reusing below one. merge for quicksort should be simplified.
return merge(merge(sortList(fakesmall.next), sortList(fakelarge.next)),fakeequal.next) ;
}
private ListNode merge(ListNode h, ListNode m){
ListNode fake = new ListNode(0), cur = fake;
while(h != null && m != null){
if(h.val < m.val){
cur.next = h;
h = h.next;
}
else{
cur.next = m;
m = m.next;
}
cur = cur.next;
}
cur.next = (h == null ? m : h);
return fake.next;
}
}
成績:8 ms,beats 42.09%,衆数8 ms,31.36%cmershenの砕けた念:配列の速い列の中でpivotは三者取中法を使用しているが,チェーンテーブルはランダムアクセスではなく,三者取中法を使用するにはチェーンテーブルを遍歴しなければならないが,かえって加速できない.