6

質問: 単一のリンク リスト (つまり、次のノードへのポインターのみを持つリスト) があります。さらに、これは循環リンク リストです (この例では、最後のノードに最初のノードへのポインターがあります)。リスト内のすべてのノードには char が含まれています。

このようなリストの例: a->b->c->b->a

このリストがパリンドロームであるかどうかを確認するにはどうすればよいですか?

私は次の解決策を考えました：

  1. リストの先頭から開始します。リストの長さを見つけてから、中間ノードを見つけます。リストの先頭から再び開始し、スタック内の要素を途中までプッシュし続けます。mid 要素と pop 要素からリストをトラバースします。ポップされた要素の値が現在のノードの値と等しい場合。そうでない場合は、false を返します。それ以外の場合は、スタックが空になり、すべての文字が確認されるまで続行します。短所：余分なスタックスペースを使用します:(

  2. リストの先頭から開始します。リストの長さを見つけてから、中間ノードを見つけます。このリストの後半を逆にします。次に、2 つのポインター (1 つは start を指し、もう 1 つは mid+1 番目の要素を指す) を使用して、値が同じかどうかを確認します。そうでない場合は、false を返します。それ以外の場合は、開始ノードに再び到達するまで続行します。短所: 元のデータ構造を変更します。

この問題に取り組むためのよりエレガントな方法はありますか (O(n) 余分なスペースを使用したり、元のリストを変更したりしないことを願っています)? 特定の実装ではなく、アルゴリズムに興味があります。

ありがとう

4

5 に答える 5

4

単一の連結リストを扱っているため、少し余分なスペースまたは多くの余分な時間を使用する必要があります。

最初のアプローチは妥当に思えますが、1 回の実行でリストの長さと回文数を判断できます。

いわゆるフロイドのサイクル発見アルゴリズムを変更します。

  • "slow" と "fast" の 2 つのポインターは、どちらもリストの先頭から始まります。低速ポインタは反復ごとに 1 つのリスト要素を進め、高速ポインタは 2 つの要素を進めます
  • 各ステップで、スロー ポインターは現在の要素をスタックにプッシュします。

高速ポインターがリストの最後に到達すると、低速ポインターはリストの中央を指すため、次のようになります。

  • スロー ポインターはリストの最後に進み、各ステップで次のようになります。
  • スタックから 1 つの要素をポップし、それを現在のリスト要素と比較します (等しくない場合は を返しfalseます) 。
  • スローポインターがリストの最後に到達した場合、それは回文です

要素数が奇数のリストには、少し余分な作業が必要です。

于 2012-09-10T09:48:48.080 に答える
0

実装を貼り付けて、相互に比較できるようにします。ここで完全なテストを行います。

/**
 * Given a circular single linked list and the start pointer, check if it is a palindrome
 * use a slow/fast pointer + stack is an elegant way
 * tip: wheneve there is a circular linked list, think about using slow/fast pointer
 */

#include <iostream>
#include <stack>
using namespace std;

struct Node
{
    char c;
    Node* next;

    Node(char c) {this->c = c;}
    Node* chainNode(char c)
    {
        Node* p = new Node(c);
        p->next = NULL;
        this->next = p;
        return p;
    }
};

bool isPalindrome(Node* pStart)
{
    Node* pSlow = pStart;
    Node* pFast = pStart;

    stack<Node*> s;
    bool bEven = false;
    while(true)
    {
        // BUG1: check fast pointer first
        pFast = pFast->next;
        if(pFast == pStart)
        {
            bEven = false;
            break;
        }
        else
        {
            pFast = pFast->next;
            if(pFast == pStart)
            {
                bEven = true;
                break;
            }
        }

        pSlow = pSlow->next;
        s.push(pSlow);

    }
    if(s.empty()) return true; // BUG2: a, a->b->a
    if(bEven) pSlow = pSlow->next; // BUG3: a->b->c->b->a, a->b->c->d->c->b->a: jump over the center pointer

    while(!s.empty())
    {
        // pop stack and advance linked list
        Node* topNode = s.top();
        s.pop();
        pSlow = pSlow->next;

        // check
        if(topNode->c != pSlow->c)
        {
            return false;
        }
        else
        {
            if(s.empty()) return true;
        }
    }

    return false;
}
于 2012-09-14T09:11:48.077 に答える
0

Linked List がサイクルを作ることを知っていて、頭から始まる回文だけを探しているので、これを自分で簡単にすることができます。

A -> B -> C -> B -> A

この場合、head のポインター (H と呼ぶ) と head.Left() のポインター (T と呼ぶ) から始めます。

ここで、ヘッド ポインター H を右に、テール ポインター T を左に動かし続けます。

リストをたどって、それらの要素の値が等しいことを確認します (つまり、回文)。

ただし、停止条件にはもう少し時間がかかります。次の 2 つのケースがあります。

  • 両方のポインターの終点が同じ要素 (つまり、要素の数が奇数)
  • H ポインターは、T のすぐ右にある要素を指しています。

したがって、H==T または H==(T.Right()) の場合は停止します。

この方法 (または同様の方法) を使用すると、各要素に一度だけアクセスできます。

リンクされたリストが循環的であるかどうかがわからない場合は、他のソリューションと同様に亀とウサギのアプローチを使用してください。

于 2012-09-10T23:56:36.733 に答える
0

これには余分なスペースは必要ないと思います。そして、これは O(n) の複雑さで実行できます。

Philip のソリューションの変更:

いわゆるフロイドのサイクル発見アルゴリズムを変更します。

"slow" と "fast" の 2 つのポインターは、どちらもリストの先頭から始まります。スロー ポインターは、反復ごとに 1 つのリスト要素を進めます。ファスト ポインターは、各ステップで 2 つの要素を進めます。スロー ポインターは、リストの最後に到達すると現在の要素をスタックにプッシュします。スロー ポインターは、リストの中央を指します。 、だから今：

リンクされたリストの先頭に別のポインターを配置し (start pointre)、ここで - 開始ポインターとスロー ポインターを 1 つずつ移動し、それらを比較します。それらが等しくない場合は、false を返します。リスト、回文です

これは O(n) 時間の複雑さであり、余分なスペースは必要ありません。

于 2013-05-03T18:13:32.073 に答える