3

インタビューでよく聞かれたと聞いてから、何かが私を悩ませてきました。単一リンクリストを逆にします。実装を確認したところ、自分が考えていたアイデアが適用できるのではないかと思っていました。

|data1|->|data2|->|data3|->|data4|->|data5|

この構造は、リンクリストの初期条件です。いつ逆転したいのかと思っていたのですが。

|data5|->|data4|->|data3|->|data2|->|data1|

したがって、 O（n）の実行時間がかかるループでは、ノード＃1とノード＃5のデータを逆にするだけで、ノード＃2とノード＃4がその役割を果たしますか？

4

7 に答える 7

4 
   typedef struct Node
   {
     char data;
     struct Node* next;
   } Node; 



    Node* reverse(Node* root)
    {
       Node* new_root = 0;
       while (root)
       {
           Node* next = root->next;
           root->next = new_root;
           new_root = root;
           root = next;
       }
       return new_root; 
    } 



int main()
{
   Node d = { 'd', 0 };
   Node c = { 'c', &d };
   Node b = { 'b', &c };
   Node a = { 'a', &b };
   Node* root = &a; 
   root = reverse(root);
   return 0;
 }
于 2012-04-23T04:51:51.030 に答える
3

アルゴリズムでは、ノード5から開始し、そこから逆方向に作業する必要があります。ただし、これは単一リンクリストです。つまり、「戻る」ポインタがありません。ノードへのO（1）アクセスがある場合でもtail、ノード4に到達するにはノード1からやり直す必要があるため、ノード5からノード4へのアクセスはそれ自体がO（N）操作になります。

したがって、単一リンクリストには適したアルゴリズムではありません。バックポインタにアクセスできる二重リンクリストの場合、O（N）の複雑さが生じます。（アルゴリズムは、各ノードに格納されているデータがコピー可能または移動可能である必要があるため、完全にタイプに依存しないわけではありません。これにより、データを交換できます。）

于 2012-04-22T18:16:45.997 に答える
3

メソッドを記述してinsert_head繰り返し使用したい。したがって、元のリストの先頭から歩いて、新しいリンクリストの先頭に追加します。したがって、元のリストの末尾が新しいリストの先頭になります。

これを行う別の方法は次のとおりです。元のリストをウォークし、ノードをスタックにプッシュします。次に、ポップしinsert_at_tailて、新しいリストに移動します。

単一リンクリストを時間内に逆方向に歩くことができないため、アルゴリズムは失敗しますO(1)。あなたが提案するように行うには、それO(n)はノードごとであり（頭から前のノードを取得する場所まで毎回歩く）、したがってリスト全体を逆にすることはO(n^2)です。

于 2012-04-22T18:16:56.710 に答える
2

尋ねられたとき、通常の制限は、おそらく3つ以下の変数を除いて余分なスペースを使用しないように、リストを元の場所に戻すことです。そのため、質問は簡単ではありません。したがって、再帰、独自の明示的なスタック、または別のLL（LL.addToHead(el)元のスタックを歩くときに使用する）を使用することはできません。

したがって、ここに良い答えがありますO（n）時間とO（1）空間：

Node reverse(Node n){//n is head; you may also get the LL
    if(null == n || null == n.next)
       return n;
    Node a=n, b=a.next, c=b.next;
    a.next=null; b.next=a;
    while(null != c){
       a=c;
       c=c.next;
       a.next=b;
       b=a;
    }
    return b;
}

ちなみに、あなたが提案する解決策はO（n ^ 2）です。

于 2012-04-23T00:31:48.250 に答える
1

スペースを使用するO(n)ソリューションがありますO(n)。線形時間で要素にアクセスする問題を回避することを検討してください。

于 2012-04-22T18:20:25.523 に答える
1

リストが異質であるか、ノードのサイズが等しくない場合、アイデアは惨めに失敗します。たとえば、次のようにします。

struct base {
   int type;
   struct base *next;
   };

struct small {
   struct base common;
   int value;
   };

struct big {
    struct base common;
    char payload[12345];
    };
于 2012-04-22T18:28:53.290 に答える
1

次の2つの理由から、最終出力での位置に基づいてノードからのデータを逆にすることはお勧めできません。

  1. リストのサイズが大きい場合、実行可能な解決策にはなりません。
  2. 任意の方法でノードにアクセスする時間は長くなります。このアプローチは、O（n）よりも時間がかかります。

この擬似コードを考えてみましょう。

reverse_list(node *head) 
{
  node *temp;
  *temp = head -> next;
  head-> next = NULL;

  while (temp != NULL) {
     swap_nodes(head, temp->next);  // this aint copying data from nodes, actual nodes are 
     swap_nodes(head, temp);        // swapped based on its and parents' next pointers  
  }
}
于 2012-04-22T19:35:05.617 に答える