5

就職の面接で、リンクリストを再帰的に反転し、新しい最初のノードを返し、新しいノードを使用しない関数をCで作成するように依頼されました。

どうすればこれを行うことができますか？

4

5 に答える 5

3

C のような構文を持つ不可知論的な言語での一般的な考え方は次のとおりです。

Node invert(Node list, Node acc) {
    if (list == null)
        return acc;
    Node next = list.next;
    list.next = acc;
    return invert(next, list);
}

上記の関数は、反転されるリストの最初のノードとそれまでの累積値を受け取り、新しく反転されたリストの先頭を返します - ノードの反転はその場で行われ、余分なスペースは割り当てられません (ローカルスタック内の変数)。次のように呼び出します。

invert(firstNodeOfList, null);

これは末尾再帰の例です。結果はaccパラメーターで収集され、各再帰呼び出しが戻ると、何もする必要がなく、蓄積された値を返すだけです。

アップデート：

関数型言語では、ローカル変数を使用せずにリストを反転する関数を作成する方が簡単で自然です。たとえば、Scheme の次のコードを見てください。consプロシージャを呼び出すときに新しいリスト ノードが作成されるという欠点があります。

(define (invert lst acc)
  (if (empty? lst)
      acc
      (invert (rest lst)
              (cons (first lst) acc))))

(invert '(1 2 3 4 5) '())
> '(5 4 3 2 1)

結論：再帰呼び出しごとに新しいノードを作成するか、新しいローカル変数を作成しますが、プログラミング言語が順次実行の式を提供し、コンパイラが評価順序を保証しない限り（@WillNessの回答を参照）、両方を排除することはできません動作するアルゴリズムを持っています。安全にプレイし、一時変数を使用して評価順序を強制し、常に正しい結果を取得することをお勧めします。

于 2012-10-03T01:21:17.773 に答える
3

nextこれは非常に単純です。リストの最後まで再帰し、毎回新しいポインターを渡し、リストの最後を返します。

struct list {
    struct list *next;
};

struct list *reverse(struct list *cur, struct list *prev) {
    struct list *next = cur->next;
    cur->next = prev;
    if(next == NULL) return cur;
    return reverse(next, cur);
}

reverse(head, NULL);
于 2012-10-03T01:21:51.440 に答える
2

「再帰的にリンクされたリスト」が何であるかわからないので、タイトルを使用して、再帰関数を使用して「リンクされたリストを逆にする」ことを想定します。

私はそれが単独でリンクされたリストであると仮定し（したがって、各要素はnext次の要素への単一のポインターを持ちます）、慣例によりnext = NULL最後の要素を取ります。 二重にリンクされたリストの場合、ポインターも処理する必要がありprevますが、基本的には同じ考え方です。 双方向にリンクされたリストを使用すると、前の要素を追跡する必要さえないため、より簡単です。各要素で 2 つのポインターを反転するだけです。

nextリストを逆にするには、一度に要素を 1 つずつ下に移動し、ポインタを反転させて前の要素を指すようにすることを想像できます。これは、現在の要素へのポインターと前の要素へのポインターをパラメーターとして受け取る再帰関数として簡単に記述できます (最初、このポインターは ですNULL)。

node* reverseList(node* head, node* prev = NULL) {
  if (head == NULL) return prev;

  std::swap(head->next, prev); // prev points to next element to process
  return reverseList(prev, head);
}
于 2012-10-03T01:38:13.460 に答える
1

やあ皆さん、以下の再帰を伴う、または伴わない逆リンクリストのプログラムを見つけてください

LINK *reverse_linked_list_recursion(LINK *head)
{
        LINK *temp;
        if (!head) {
                printf("Empty list\n");
                return head;
        }
        else if (!head->next)
                return head;
        temp = reverse_linked_list_recursion(head->next);
        head->next->next = head;
        head->next = NULL;
        return temp;
}

LINK *reverse_linked_list_without_recursion(LINK *head)
{
        LINK *new, *temp;
        if (!head) {
                printf("No element in the list\n");
                return head;
        }
        else {
                new = head;
                while (head->next) {
                        temp = head->next;
                        head->next = temp->next;
                        temp->next = new;
                        new = temp;
                }
        }
        return new;
}
于 2013-08-13T06:49:59.060 に答える
0

したがって、オスカー・ロペスの答えのバリエーションは次のとおりです。

Node invert(Node list, Node acc) 
{
    if (!list) 
        return acc; 
    return invert(list.next, ((list.next=acc),list));
}

一連の式(a,b)は最後の値を返し、左から右に評価されます。

これは、関数の引数の評価順序がleft-to-rightであることを保証するコンパイラでのみ機能します。right-to-leftの場合、 への引数をinvert交換する必要があります。

評価順序が非決定的である場合、これは機能しません。C 標準は明らかにこの順序を未指定のままにしていますが、一部のコンパイラでは独自の方法がある場合があります。コンパイラについてこれを知っているかもしれませんが、それは移植性がなく、コンパイラも将来これを変更する可能性があります。そのようなコードを書くことは嫌われます。多分それはあなたのインタビュアーがあなたから聞きたかったことです. 彼らはそのようなトリックが好きで、あなたがどのように反応するかを見たいと思っています。

評価順序を制御する通常の方法は、一時変数を使用することです。

于 2012-10-03T23:29:30.740 に答える