0

おそらく同じ質問の投稿がたくさんありますが、問題はそれがによって行われなければならないと言っています

 node* reverseList (node * lh)
                              {
                               if(lh==NULL)............ ;

                                else if (lh->next==NULL)...........;

                                else ...........;
                              }

3つの空白を埋める必要があります最初の2つは単純です

return NULL

と

return lh

それぞれに

1つの方法は、単に下に移動してポインターを逆にすることですが、その場合、バックトラックした後でもテールをそのまま維持するにはどうすればよいですか？それは可能ですか？

4

3 に答える 3

3

再帰的な問題を解決する秘訣は、すでに完了したふりをすることです。この宿題を自分で解決するには、次の3つの質問に答える必要があります。

  • 空のリストをどのように元に戻しますか？lh（つまり、に設定されたリストNULL）？
  • アイテムが1つしかないリストをどのように逆にしますか？
  • 誰かが最初のアイテムを除いてリストのすべてのアイテムを元に戻すことができる場合、最初のリストの最初のアイテムをリストの事前に反転された「テール」部分にどこに追加しますか？

あなたはすでに最初の2つに答えました：NULLそしてそれlhは正しい答えです。次に、3番目のものについて考えます。

else {
    node *reversedTail = reverseList(lh->next);
    ...
}

この時点でreversedTail、リストの事前に反転されたテールが含まれています。あなたがする必要があるのは、lh-> NULLの隣に設定し、それをあなたが保持しているリストの後ろに追加し、そして返すことreversedTailです。最終的なコードは次のようになります。

else {
    node *reversedTail = reverseList(lh->next);
    node *p = reversedTail; 
    while (p->next) p = p->next;
    p->next = lh;
    lh->next = NULL;
    return reversedTail;
}
于 2011-12-12T17:02:32.820 に答える
2

私はこれがそれに答えると思います：

node *reverseList(node *lh)
{
    if (!lh) return NULL;
    else if (!lh->next) return lh;
    else {
        node *new_head = reverseList(lh->next);
        lh->next->next = lh;
        lh->next = NULL;
        return new_head;
    }
}

反転されたリストの先頭、つまり元のリストの末尾を返します。

head = reverse_list(head);
于 2011-12-12T17:38:48.603 に答える
1

以下は、単一のリンクリストの反転を行うAPIです。これは、私が見た中で最高のアルゴリズムの1つです。

void iterative_reverse() 
{ 

    mynode *p, *q, *r; 

    if(head == (mynode *)0) 
    { return; 
    } 

    p = head; 
    q = p->next; 
    p->next = (mynode *)0; 

    while (q != (mynode *)0) 
    { 
        r = q->next; 
        q->next = p; 
        p = q; 
        q = r; 
    } 
    head = p; 
 }
于 2011-12-12T17:02:20.420 に答える