これは（再び）インタビューの質問です。
単一に接続されたリンクリストが与えられた場合、リスト内で最大の回文を見つけます。（回文の長さは偶数であると想定できます）
私が行った最初のアプローチは、スタックを使用することでした。最初からリストをトラバースし、文字を押し続けます。スタックの一番上の文字がリンクリストの次の文字と同じであることがわかったら、ポップを開始し（そしてリンクリストポインタをインクリメントし）、一致する文字の数にカウントを設定します。不一致が見つかったら、スタックからポップしたすべての文字をプッシュバックし、プッシュおよびポップ操作を続行します。このメソッドの最悪の場合の複雑さはO（n2）です。たとえば、リンクリストが同じ文字の文字列である場合です。
空間と時間の複雑さを（いくつかの一定の要因によって）改善するために、リンクリストを配列にコピーし、配列内で最大サイズのパリンドロームを見つけることを提案しました。これもO（n2）時間の複雑さとO（n）空間の複雑さを取ります。
私を助けるためのより良いアプローチはありますか？:(
次のように、O（1）空間の複雑さを伴うO（n²）アルゴリズムを思い付くことができます。
考えてみてくださいf→o→b→a→r→r→a→b：
訪問中にリンクを逆にしてリストをウォークスルーします。で始まりx=f、y=f.next：
x.next = nullfo→b→a→r→r→a→b ^ ^ | \ xy両方のリスト（xとy）が等しいリンクの数を確認します。
tmp=y.next、、、）たとえば、2番目のステップでは、とが生成さy.next=xれx=yます。ここで、回文であるかどうかをもう一度確認して、続行します。y=tmpf←o b→a→r→r→a→bx=oy=bf←o←b a→r→r→a→bf←o←b←a r→r→a→bf←o←b←a←r r→a→bわーい ：）リストを再度復元する必要がある場合は、O（n）で再度逆にします。
これは、 O(N)時間の複雑さを持つよく分析された問題です。
str元の文字列を逆にすることができます（としましょうstr_reversed）次に、問題は次のように変換されます。とで最も長い共通部分文字列を見つけます。strstr_reversed
リストを配列にコピーする場合、次のことが役立つ可能性があります。偶数の長さの回文のみを考慮するため、この場合を想定しています。しかし、この手法は、奇数の長さのパリンドロームで機能するように簡単に拡張できます。
回文の実際の長さではなく、半分の長さを保存するので、左右に何文字移動できるかがわかります。
単語を考えてみましょう：aabbabbabab。最長の回文を探しています。
a a b b a b b a b a b (spaces for readability)
°^° start at this position and look to the left/right as long as possible,
1 we find a palindrome of length 2 (but we store "1")
we now have a mismatch so we move the pointer one step further
a a b b a b b a b a b
^ we see that there's no palindrome at this position,
1 0 so we store "0", and move the pointer
a a b b a b b a b a b
° °^° ° we have a palindrome of length 4,
1 0 2 so we store "2"
naively, we would move the pointer one step to the right,
but we know that the two letters before pointer were *no*
palindrome. This means, the two letters after pointer are
*no* palindrome as well. Thus, we can skip this position
a a b b a b b a b a b
^ we skipped a position, since we know that there is no palindrome
1 0 2 0 0 we find no palindrome at this position, so we set "0" and move on
a a b b a b b a b a b
° ° °^° ° ° finding a palindrome of length 6,
1 0 2 0 0 3 0 0 we store "3" and "mirror" the palindrome-length-table
a a b b a b b a b a b
^ due to the fact that the previous two positions hold "0",
1 0 2 0 0 3 0 0 0 we can skip 2 pointer-positions and update the table
a a b b a b b a b a b
^ now, we are done
1 0 2 0 0 3 0 0 0 0
つまり、回文の位置が見つかるとすぐに、テーブルの一部を推測できます。
もう一つの例：aaaaaab
a a a a a a b
°^°
1
a a a a a a b
° °^° °
1 2 1 we can fill in the new "1" since we found a palindrome, thus mirroring the
palindrome-length-table
a a A A a a b (capitals are just for emphasis)
^ at this point, we already know that there *must* be a palindrome of length
1 2 1 at least 1, so we don't compare the two marked A's!, but start at the two
lower-case a's
私のポイントは、パリンドロームを見つけるとすぐに、パリンドロームの長さのテーブル（少なくとも一部）をミラーリングして、新しいキャラクターに関する情報を推測できる可能性があるということです。このようにして、比較を保存できます。
O(n^2) アルゴリズムは次のとおりです。
リストを双方向リンク リストに変換する
回文の長さが均等になるには、2 つの同じ文字が隣り合っている必要があります。したがって、隣接する文字の各ペア (n-1 個) を反復処理し、反復ごとに、文字が同一である場合、真ん中の文字がこれら 2 つである最大の回文を見つけます。
O（n）時間で再帰を使用してそれを行いました。私はこれをやっています、
コード：
#include<stdio.h>
#include<malloc.h>
struct node {
int data;
struct node *link;
};
int append_source(struct node **source,int num) {
struct node *temp,*r;
temp = *source;
if(temp == NULL) {
temp = (struct node *) malloc(sizeof(struct node));
temp->data = num;
temp->link = NULL;
*source = temp;
return 0;
}
while(temp->link != NULL)
temp = temp->link;
r = (struct node *) malloc(sizeof(struct node));
r->data = num;
temp->link = r;
r->link = NULL;
return 0;
}
int display(struct node *source) {
struct node *temp = source;
while(temp != NULL) {
printf("list data = %d\n",temp->data);
temp = temp->link;
}
return 0;
}
int copy_list(struct node **source, struct node **target) {
struct node *sou = *source,*temp = *target,*r;
while(sou != NULL) {
if(temp == NULL) {
temp = (struct node *) malloc(sizeof(struct node));
temp->data = sou->data;
temp->link = NULL;
*target = temp;
}
else {
while(temp->link != NULL)
temp = temp->link;
r = (struct node *) malloc(sizeof(struct node));
r->data = sou->data;
temp->link = r;
r->link = NULL;
}
sou = sou->link;
}
return 0;
}
int reverse_list(struct node **target) {
struct node *head = *target,*next,*cursor = NULL;
while(head != NULL) {
next = head->link;
head->link = cursor;
cursor = head;
head = next;
}
(*target) = cursor;
return 0;
}
int check_pal(struct node **source, struct node **target) {
struct node *sou = *source,*tar = *target;
while( (sou) && (tar) ) {
if(sou->data != tar->data) {
printf("given linked list not a palindrome\n");
return 0;
}
sou = sou->link;
tar = tar->link;
}
printf("given string is a palindrome\n");
return 0;
}
int remove_list(struct node *target) {
struct node *temp;
while(target != NULL) {
temp = target;
target = target->link;
free(temp);
}
return 0;
}
int main()
{
struct node *source = NULL, *target = NULL;
append_source(&source,1);
append_source(&source,2);
append_source(&source,1);
display(source);
copy_list(&source, &target);
display(target);
reverse_list(&target);
printf("list reversed\n");
display(target);
check_pal(&source,&target);
remove_list(target);
return 0;
}
最初にリンク リストの中間点を見つけます。この場合、リンク リストをトラバースし、ノードの数を数えます。
ノードの数がNであるとしましょう。中間点はN/2になります。
次に、中間ノードまでトラバースし、O(n) の複雑さでその場で実行できる最後までリンクされたリストを反転し始めます。
次に、start から midpoint までの要素を midpoint から last までの要素と比較します。それらがすべて等しい場合、文字列は回文であり、そうでない場合は中断します。
時間の複雑さ:- O(n)
スペースの複雑さ:- O(1)