Leetcode Sort Listチェーンテーブル集計ソート
2310 ワード
Sort List
Sort a linked list in O(n log n) time using constant space complexity.
この問題はquicksortではACができないようで、集計ソートしか使えません.
前は難しい問題だと思っていました.
こんなに長い間アルゴリズムを訓練していたのに,やっと力が上がった.まだ化境に達していないが、以前は何が並べ替えられているのか、急速な並べ替えが難しいような気がした.今では、いつでもこのようなアルゴリズムを書くことができます.しかもコードは基本的に整っていて、はっきりしていて、O(∩∩)O~
もともとアルゴリズムは練習したもので,丸暗記ではない.
私が言った化境は、ある日どんな難題でも簡単に学んだアルゴリズムを利用して、優雅なコードに変換することができると思っています.その時、すべてのアルゴリズムはすでに融通がきいていて、すべての問題の差が多くないのは同じで、すべてのアルゴリズムも多くありません.ほほほ.
Sort a linked list in O(n log n) time using constant space complexity.
この問題はquicksortではACができないようで、集計ソートしか使えません.
前は難しい問題だと思っていました.
こんなに長い間アルゴリズムを訓練していたのに,やっと力が上がった.まだ化境に達していないが、以前は何が並べ替えられているのか、急速な並べ替えが難しいような気がした.今では、いつでもこのようなアルゴリズムを書くことができます.しかもコードは基本的に整っていて、はっきりしていて、O(∩∩)O~
もともとアルゴリズムは練習したもので,丸暗記ではない.
私が言った化境は、ある日どんな難題でも簡単に学んだアルゴリズムを利用して、優雅なコードに変換することができると思っています.その時、すべてのアルゴリズムはすでに融通がきいていて、すべての問題の差が多くないのは同じで、すべてのアルゴリズムも多くありません.ほほほ.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *sortList(ListNode *head)
{
if (!head || !head->next) return head;
ListNode *slow = head;
ListNode *fast = head->next;
while (fast->next)
{
slow = slow->next;
fast = fast->next;
if (fast->next) fast = fast->next;
}
ListNode *h2 = slow->next;
slow->next = NULL;
head = sortList(head);
h2 = sortList(h2);
head = combinTwoList(head, h2);
return head;
}
ListNode *combinTwoList(ListNode *n1, ListNode *n2)
{
ListNode dummy(0);
dummy.next = n1;
ListNode *pre = &dummy;
while (pre->next && n2)
{
if (pre->next->val > n2->val)
{
ListNode *t = n2->next;
n2->next = pre->next;
pre->next = n2;
pre = n2;
n2 = t;
}
else pre = pre->next;
}
if (n2) pre->next = n2;
return dummy.next;
}
};
//2014-2-19 update
ListNode *sortList(ListNode *head)
{
if (!head || !head->next) return head;
ListNode *slow = head;
ListNode *fast = head;
while (fast->next && fast->next->next)
{
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = nullptr;
head = sortList(head);
fast = sortList(fast);
return mergeList(head, fast);
}
ListNode *mergeList(ListNode *h1, ListNode *h2)
{
ListNode dummy(0);
ListNode *p = &dummy;
while (h1 && h2)
{
if (h1->val < h2->val)
{
p->next = h1;
h1 = h1->next;
}
else
{
p->next = h2;
h2 = h2->next;
}
p = p->next;
}
if (h1) p->next = h1;
else p->next = h2;
return dummy.next;
}