C++ Nodeのポインタをつなぎ変える時にTLEになる
解決したいこと
C++でのTLEを解決したい。
発生している問題・エラー
C++でNodeを使って連結リストを作っていたのですが、ある新しいNodeをポインタをつなぎ変えて挿入する時TLEになってしまいました。
該当するソースコード
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define rep(i,n) for(i = 0; i < (n); ++i)
#define reps(i,s,n) for(i = s; i < (n); ++i)
struct Node {
int key;
Node *next, *prev;
};
Node *nil;
Node* listSearch(int key){
Node *skey = nil->next;
while(skey != nil && skey->key != key) skey = skey->next;
return skey;
}
void init(){
nil = (Node *)malloc(sizeof(Node));
nil->next = nil;
nil->prev = nil;
}
void printList(){
Node *cur = nil->next;
while(cur != nil){
if(cur->next == nil) printf("%d ",cur->key);
else printf("%d",cur->key);
}
printf("\n");
}
void deleteNode(Node *t){
if(t == nil) return;
t->prev->next = t->next;
t->next->prev = t->prev;
free(t);
}
void deleteFirst(){
deleteNode(nil->next);
}
void deleteLast(){
deleteNode(nil->prev);
}
void deleteKey(int key){
deleteNode(listSearch(key));
}
void insert(int key){
Node* x = (Node *)malloc(sizeof(Node));
x->key = key;
x->next = nil->next;
nil->next->prev = x;
nil->next = x; <-ここでTLE
x->prev = nil;
}
int main(){
int i,j,key,n,size = 0;
char com[20];
scanf("%d", &n);
init();
rep(i,n){
scanf("%s%d",com, &key);
if(com[0] == 'i') insert(key); <-ここのinsert関数
else if(com[6] == 'F') deleteFirst();
else if(com[6] == 'L') deleteLast();
else deleteKey(key);
}
printList();
return 0;
}
自分で試したこと
nil->next = x の文だけ抜いて実行するとTLEにならずに実行されました。
0
