0

重複の可能性:
単一のリンクされたリストが回文であるかどうか

文字項目を持つリンク リストがあるとします。そのリンク リスト内の文字が回文かどうかを調べる必要があります。リンクリストがこれに適した構造ではないことは知っていますが、リンクリストがある場合はどうすればよいですか?

例えばa-b-c-b-a

二重リンク リストは簡単です。先頭と末尾から始めます。

ptrh=head ptrt=tail
if(ptrh->item==ptrt->item)

と

ptrh->ptrh->frwdlink
ptrt->ptrt->bcklink

しかし、リンクされたリストが 1 つしかない場合はどうなるでしょうか。それを実装する方法は？

4

3 に答える 3

4

リストのサイズがわかれば、真ん中が何かがわかります。次に、途中まですべての文字をキャッシュし、途中で逆の順序で表示されるようにします。

于 2012-08-10T23:11:36.987 に答える
3

一時的な配列を作成できますか? リンクされたリスト内のすべての項目を配列に入れ、インデックス n とインデックス (長さ - n) を比較します。

var ptr = head; var array = [];

while (ptr != null)
{
  array.push(ptr.item);
  ptr = ptr.next;
}

for (var i = 0; i < array.length / 2; i++)
{
  if (array[i] != array[array.length - i])
    return (false);
}

return (true);
于 2012-08-10T23:16:35.800 に答える
2

初めてリストを調べているときに、ノードの逆順でリストを作成できます。

次に、元のリストと逆リストの最初の n/2+1 ノードを比較します

于 2012-08-10T23:15:04.140 に答える