2

最近、面接でこんな質問をされました。私ができることは、0 から 9 までのリンクされたリストから 9 から 1 までトラバースすることだけです。コードは次のとおりです。

#include <iostream>

typedef struct node {                                                               
      int data;               // will store information
      node *next;             // the reference to the next node
};  
node *head;

int printList(node *traverse) {
    if (traverse->next == NULL) {
        return -1;
    }
    traverse=traverse->next;
    printList(traverse);

    cout << traverse->data << endl;
    return 0;
}

int main() {
    node *temp = NULL;
    node *begin = NULL;      
    for (int i = 0; i < 10; i++) {
        temp = new node;
        temp->data = i;
        if (begin == NULL) {
            begin = temp;
        }
        if (head != NULL) {
            head->next = temp;
        }
        head = temp;
        head->next = NULL;
    }
    head = begin;
    printList(head);
    return 0;
}

printList()1)再帰関数で 0 (最初の要素) を出力するにはどうすればよいですか?

printList()2)再帰関数を while ループに置き換えるにはどうすればよいですか?

3) インタビューで尋ねられた場合、main()関数には適切なノードの初期化と挿入がありますか?

4

7 に答える 7

17

これを達成するための 4 つの方法があり、それぞれに独自のメリットがあります。

再帰

void print_list(node* traverse)
{
    if (traverse == NULL) return;
    print_list(traverse->next);
    std::cout << traverse->data << std::endl;
}

これはおそらく最初に頭に浮かんだ答えです。ただし、プロセス スタックのサイズには制限があるため、再帰の制限はかなり低くなります。大きなリストは、スタック オーバーフローを引き起こします。これは C++ ではあまり良い設計ではありません。

反復

void print_list(node *n)
{
    using namespace std;
    deque<node*> res;
    for(;n != NULL; n = n->next) res.push_back(n);
    for_each(res.rbegin(), res.rend(), [](node* n){cout << n->data << endl;});
}

もちろん、反復的な方法で行いたい場合は、ノード ポインターを自分で (プロセス ヒープに) スタックする必要があり、このジョブをcall stackに委任しないでください。このメソッドを使用すると、はるかに大きなリストを出力でき、計算では O(n) になります。ただし、メモリ使用量は O(n) ですが、O(n) メモリを使用するリストが既にあります。したがって、これは問題になりません。ただし、メモリの消費を避ける必要がある場合があります。これが次のアイデアにつながります。

二重反復

void print_list(node *head)
{
    node* last = NULL;
    while(last != head)
    {
        node* current = head;
        while(current->next != last)
            current = current->next;
        std::cout << current->data << std::endl;
        last = current;
    }
}

O(n^2) の複雑さがあるため、これはばかげたソリューションに見えるかもしれませんが、それは計算の複雑さです。O(1) メモリの複雑さがあり、実際のコンテキストと正確な問題によっては、必要な答えになる場合があります。しかし、この O(n^2) の複雑さには多くの代償が伴います。特に n が非常に大きい場合は、別の O(n) 割り当てを避けたいでしょう。これが最後のアイデアにつながります。

コンテナをハックする

void print_list(node *head)
{
    node* last = NULL;
    for(node* next; head != NULL; head = next)
    {
        next = head->next;
        head->next = last;
        last = head;
    }
    for(node* next; last != NULL; last = next)
    {
        next = last->next;
        last->next = head;
        head = last;
        cout << last->data << endl;
    }
}

最初にコンテナを変更してから、新しい順序で繰り返します。単一リンクのリストでは、リンクを反転させてから、リンクを反転させながら逆方向に繰り返すことができます。その優れた点は、コンピューティングでは O(n)、メモリでは O(1) のままであることです。問題は、これを実行している間に完全なコンテナーを無効にすることです: 出力操作はリストを一定のままにしない: これは例外セーフではありません: 反復の途中で操作が失敗した場合、リストはもう有効ではありません。これは、問題に応じて問題になる場合とそうでない場合があります。

于 2013-07-03T15:43:13.583 に答える
4

while ループを使用してリストを逆方向にトラバースするための古いトリックがあります。

順方向にループをたどりますが、各ノードを離れるときにリンクを逆にします。つまり、現在の値 (次のノードへのポインター) を取得しますが、前のノードへのポインターが含まれるように設定します。ノード。リストの最後に到達すると、反対方向に進む片方向リストになります。つまり、ポインターをたどるとリストの最初に戻ります。

次に、最初に戻って、各ノードの値を表示し、(再び) リンクを逆にします。終了すると、リストは開始時の状態になり、リンクは最初から最後まで続きます。

ただし、これは (1 つの明らかな例として) マルチスレッド コードで問題を引き起こす可能性があることに注意してください。リストの最初から最後まで、そして最初に戻る全体のトラバーサルは、単一のアトミック操作として処理する必要があります。2 つのスレッドがリストを同時にトラバースしようとすると、非常に悪いことが起こります。同様に、この例外を安全にすることも、やや困難な場合があります。

IOW、これらは実際の問題に対する効果的な解決策になることはめったにありません（ただし、一般的にリンクされたリストにも同じことが当てはまります）。ただし、それらは、ばかげた連結リストのトリックを実行できることをインタビュアーに示す効果的な方法です。

于 2013-07-03T15:43:38.497 に答える
1

リストが [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] の場合:

1)リストを反転して出力したい場合、printList は次のようになります。

int printList(node* traverse)
{
    if (!traverse)
        return (-1);
    printList(traverse->next);
    std::cout << traverse->data << std::endl;
    return (0);
}

2）出力する結果文字列の先頭にすべてのノードのデータを連結するなど、本当に醜いことをしない限り、whileループでは実際には不可能です。

3)あなたのメインは私にはとても奇妙に思えます。あなたの「ヘッド」変数がグローバルである理由がわかりません。メイン自体ではないのはなぜですか?

最後になりましたが、なぜ std::list を使用しないのでしょうか?

于 2013-07-03T15:22:09.370 に答える
1

面接でこんな質問をされました。single list両端から同時に横断することを目的としていました。したがって、単一のリストを逆にすることはオプションではありませんでした。また、メモリ空間の複雑さはO(1). O(n^2)時間の複雑さを持つネストされたループで解決しようとしています。ただし、より効果的な方法はXOR linked list、@chuckcottrill と @jerry-coffin によって言及されたものを使用することです。xorノードの prev および next ポインタに操作を適用することで、単一リストを XOR 連結リストに変換できます。XOR 演算の次のプロパティに基づく XOR リンク リスト。

a^a^b = b (左側の順序は重要ではありません)

単一のリスト内のノードとその隣接ノードを考えてみましょう:

  • X: 前のノードのアドレス、Y: 次のノードのアドレス
  • XOR リストへの変換中 Y' = X^Y (Y': Y の新しい値)
  • XOR リスト Y^(Y') =Y^Y^X=X を逆トラバース中

したがって、前のノード (X) に到達し、逆トラバーサルを実行できます。次のコードは、単一のリストを XOR リンク リストに変換し、逆方向のトラバーサルを行います (順方向のトラバーサルも同時に可能です)。

    node* curr = head;
    node* prev = NULL;
    node* next= curr->next;

    while (curr) {
        next = curr->next;
        // apply xor to prev and next   
        curr->next = (node*)((uintptr_t)(prev)^(uintptr_t)(next));
        // move pointers forward
        prev = curr;
        curr = next;
    }
    // prev becomes tail node 
    
    // -- Reverse Traversal --
    curr = prev ; // curr points to tail 
    prev = NULL;
    node* temp;
    
    while (curr) {
        cout << curr->data << " ";
        temp = curr;
        // apply xor to prev and next  
        curr = (node*)((uintptr_t)(prev)^(uintptr_t)(curr->next));
        prev = temp;
    }
于 2021-11-29T04:39:10.480 に答える
-1

1) 変更

if (traverse->next == NULL)

に

if (traverse == NULL)

2)

while(traverse != NULL) {
    // print sth
    traverse = traverse->next;
}

3) 私には問題ないようです。main の外で head を宣言するのはなぜですか?

于 2013-07-03T15:15:39.757 に答える
-1 
traverse->next = traverse;

あなたが使用できる可能な解決策。別の可能性として、

traverse = (traverse->next)-    (traverse);

ただし、オーバー/アンダーフローのエラー チェックが必要です。

于 2015-04-15T01:12:38.997 に答える