leetcodeチェーンテーブルソート
チェーンテーブルを並べ替え、集計で並べ替えます.問題は空間時間複雑度がO(nlogn)であることを要求するが,空間複雑度がO(1)である.
1.自分で書いたプログラムで、時間の複雑度はO(nlogn)ですが、空間の複雑度はO(n)です.
中間ノードは、高速ポインタ(2ステップと1ステップ)で見つけます.しかし、最後に並べ替えた部分をコピーして並べた部分を元のチェーンテーブルに貼り付けると、この方法は不器用で、空間の複雑さを増やし、テーマの要求を満たしていない.
leetcodeが提出したときruntime errorと言いましたが、自分で実行するのはパスで、時間の複雑さのせいか、後で変更する必要があります
2.leetcode中大神のコード、ここに貼るのは自分が後で探しやすいためです
それは底から上へ、まとめられています.Stepは1,2,4,8....
残りの補足部分、リンクの初期化と印刷部の出力
3.最後に提出したバージョンは、実行可能でわかりやすく、他人から見たものです
1.自分で書いたプログラムで、時間の複雑度はO(nlogn)ですが、空間の複雑度はO(n)です.
中間ノードは、高速ポインタ(2ステップと1ステップ)で見つけます.しかし、最後に並べ替えた部分をコピーして並べた部分を元のチェーンテーブルに貼り付けると、この方法は不器用で、空間の複雑さを増やし、テーマの要求を満たしていない.
leetcodeが提出したときruntime errorと言いましたが、自分で実行するのはパスで、時間の複雑さのせいか、後で変更する必要があります
void mergesort(ListNode* head, ListNode* as, ListNode* ae, ListNode* bs, ListNode* be){
vector<int> vec;
ListNode* ps = as;
ListNode* pe = be;
int i= 0;
int anum = ae - as;
int bnum = be - bs;
int ia = 0, ib = 0;
while(ia <= anum && ib <= bnum){
if(as->val <= bs->val){
vec.push_back(as->val);
as = as->next;
ia++;
}
else{
vec.push_back(bs->val);
bs = bs->next;
ib++;
}
}
while(ia <= anum){
vec.push_back(as->val);
as = as->next;
ia++;
}
while(ib <= bnum){
vec.push_back(bs->val);
bs = bs->next;
ib++;
}
int pnum = pe - ps;
int ip = 0;
while(ip <= pnum){
ps->val = vec[i++];
ps = ps->next;
ip++;
}
}
void merge(ListNode* head,ListNode* start, ListNode* end){
if(start < end){
ListNode* former=start, * latter = start;
int snum = end - start;
int latt = 0;
while(latt + 2 <= snum){
former = former->next;
latter = latter->next->next;
latt = latt + 2;
}
if(latt+1 == snum){
latter = latter->next;
}
merge(head,start,former);
merge(head,former->next,latter);
mergesort(head,start,former,former->next,end);
}
else
return;
}
2.leetcode中大神のコード、ここに貼るのは自分が後で探しやすいためです
それは底から上へ、まとめられています.Stepは1,2,4,8....
/**
* merge the two sorted linked list l1 and l2,
* then append the merged sorted linked list to the node head
* return the tail of the merged sorted linked list
*/
ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){
ListNode *cur = head;
while(l1 && l2){
if(l1->val > l2->val){
cur->next = l2;
cur = l2;
l2 = l2->next;
}
else{
cur->next = l1;
cur = l1;
l1 = l1->next;
}
}
cur->next = (l1 ? l1 : l2);
while(cur->next) cur = cur->next;
return cur;
}
/**
* Divide the linked list into two lists,
* while the first list contains first n ndoes
* return the second list's head
*/
ListNode* split(ListNode *head, int n){
//if(!head) return NULL;
for(int i = 1; head && i < n; i++) head = head->next;
if(!head) return NULL;
ListNode *second = head->next;
head->next = NULL;
return second;
}
ListNode *sortList(ListNode *head) {
if(!head || !(head->next)) return head;
//get the linked list's length
ListNode* cur = head;
int length = 0;
while(cur){
length++;
cur = cur->next;
}
ListNode dummy(0);
dummy.next = head;
ListNode *left, *right, *tail;
for(int step = 1; step < length; step <<= 1){
cur = dummy.next;
tail = &dummy;
while(cur){
left = cur;
right = split(left, step);
cur = split(right,step);
tail = merge(left, right, tail);
}
}
return dummy.next;
}
残りの補足部分、リンクの初期化と印刷部の出力
/**
* Definition for singly-linked list.*/
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* init(int a[], int n){
ListNode* q = NULL, *head = NULL;
for(int i = 0; i < n; i++){
ListNode* p = new ListNode(0);
p->val = a[i];
if(i==0){//
head = q = p;
continue;
}
q->next=p;
q = q->next;
}
q->next = NULL;
return head;
}
void prints(ListNode* head){
while(head){
cout<<head->val<<" ";
head = head->next;
}
}
int main(int argc, const char * argv[]) {
int a[]={2,5,3,7,9,4,1,8};
//int a[]={2,1};
ListNode* head =new ListNode(0);
head=init(a,8);
ListNode* L = sortList(head);
prints(L);
return 0;
}
3.最後に提出したバージョンは、実行可能でわかりやすく、他人から見たものです
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void mergesort(ListNode* head, ListNode* as, ListNode* ae, ListNode* bs, ListNode* be){
vector<int> vec;
ListNode* ps = as;
ListNode* pe = be;
int i= 0;
int anum = ae - as;
int bnum = be - bs;
int ia = 0, ib = 0;
while(ia <= anum && ib <= bnum){
if(as->val <= bs->val){
vec.push_back(as->val);
as = as->next;
ia++;
}
else{
vec.push_back(bs->val);
bs = bs->next;
ib++;
}
}
while(ia <= anum){
vec.push_back(as->val);
as = as->next;
ia++;
}
while(ib <= bnum){
vec.push_back(bs->val);
bs = bs->next;
ib++;
}
int pnum = pe - ps;
int ip = 0;
while(ip <= pnum){
ps->val = vec[i++];
ps = ps->next;
ip++;
}
}
void merge(ListNode* head,ListNode* start, ListNode* end){
int hnum = end - start;
if(hnum > 0){
ListNode* former=start, * latter = start->next;
while(latter!= NULL && latter->next != NULL){
former = former->next;
if(latter->next->next == NULL)
latter = latter->next;
else
latter = latter->next->next;
}
merge(head,start,former);
merge(head,former->next,latter);
mergesort(head,start,former,former->next,end);
}
else
return;
}
ListNode* sortList(ListNode* head) {
if(head == NULL || head->next == NULL)
return head;
ListNode* p = head;
while(p->next != NULL)
p = p->next;
merge(head,head,p);
return head;
}
};