list - 単一リンクリストを再帰的に逆にする

Question

したがって、コンピュータープログラミングのレッスンの一環として、このアルゴリズムに基づいて、ノードの単一リンクリストを逆にする必要があります。

「リストを順番にたどって、各ノードを削除し、新しい最初のノードとして挿入します。」

私はこれを繰り返し行うことができましたが、教授はこれを再帰的に行うように求めています。再帰を理解するために最善を尽くしていますが、うまく機能していません。

そのため、コーディングを反復から再帰的であると信じているものに変更しました

private void recursiveReverse2(Node p)
{
    Node lead = p;
    Node tail = p;

    if (p == null)
    {
        return;
    }

    if (p.next == null)
    {
        return;
    }

    current = tail.next;
    lead = current.next;
    current.next = null;
    tail.next = lead;
    current.next = head;
    head = current;
    recursiveReverse2(tail);
}


public void reverse2()
{
    toggle();   //swithces sort of list from ascending-descending
    recursiveReverse2(head); //head initialized at start of class
}

基本的に、私が実際に行ったことは再帰であるかどうかを尋ねたかったのです。recursiveReverse2()は機能しますが、再帰を実装したかどうかはわかりません。

score 1 · Accepted Answer

再帰を記述するときは、通常、最終ケースについて考えてから、再帰ケースを最後に記述するのが最善です。再帰に関するもう 1 つの点は、結果を返すのに非常に役立つことです。

はい、あなたのソリューションは技術的に再帰的ですが、コードが機能するとは思いません。行current.next = headでは、このコードが表示されていないクラスにない限り、 head は定義されていません。さらに悪いことに、関数の最初とtail = p最後にで再帰が呼び出されるtailため、無限ループになる可能性があります。したがって、無限ループになります。せいぜいこれは長さ 3 のリストを逆にしますが、任意の長さのリストではありません。

Java では、再帰関数を開始するために「ヘルパー」関数が必要になることがよくあります。まず、次のノードクラスを想定します。

public class Node{
    public object data;
    public Node next;
}

そして、問題のステートメントを考えると、次のポインターだけで、データポインターで遊ぶことは許可されていないと思います。このコードは Node.js 以外のクラスになります。

public Node recursiveReverse(Node p)
{
    return helperReverse(p, null);
} 

private Node helperReverse(Node p, Node previous)
{
    if (p == null)
    {
        return p;
    }
    else if (p.next == null)
    {
        p.next == previous;
        return p;
    }
    else
    {
        Node next = p.next;
        p.next = previous;
        return helperReverse(next, p);
    }
}

Node クラスに組み込むとさらに良くなります。

public class Node{
    public object data;
    public Node next;

    public Node reverse() {
        return reverse1(null);
    } 

    private Node reverse1(Node previous) {
        if (next == null) {
            next == previous;
            return this;
        }
        else {
            Node other = next;
            next = previous;
            return reverse1(other, this);
        } 
    }

}

楽しみ！

score 0 · Accepted Answer

一時ノードを使用せずにリストを逆にします。

struct node* reverse_helper(struct node *ptr, struct node **head)
{
        if(ptr->next == NULL)
            *head = ptr;
        else 
            (reverse(ptr->next,head))->next = ptr;

        return ptr;
}        

/*Call reverseList Function with your List head reference */
void reverseList(struct node **head)
{
     struct node *ptr = reverse_helper(*head,head);
     ptr->next = NULL;     
}

score 0 · Accepted Answer

次のポインターを持つノードクラスがあると仮定したC ++の再帰コード....最初に再帰関数を呼び出す2つの関数と、単一リンクリストを逆にする2番目の再帰関数を呼び出す

 void callReverse()
 {
  node *tempPointer=head;
  head=NULL;
  reverse(tempPointer);
 }

2番目の関数は再帰関数です

 void reverse(node * pointer)
 {

  if(pointer->next==NULL)   //this case works only when linked list has a single node
  {
    if(head==NULL)
     head=pointer; 
  }

  else if(pointer->next->next!=NULL)
  {
    reverse(pointer->next)  //recursive call
  }

  if(head==NULL)
   head=pointer->next;

  pointer->next->next=pointer;

  pointer->next=NULL;

 }

私にあなたの提案をしてください...

score 0 · Accepted Answer

これはどう：

void driver(Node head)
{
    rec_rev_ll(head,NULL); 
}

void rec_rev_ll(Node head, Node prev) 
{
    Node tmp = head->next;
    if(tmp == NULL) // Ends recursion when end of linked list is reached.
    {
        head->next = prev;
        return;
    }
    head->next = prev;
    rec_rev_ll(tmp,head);
}

短くて甘い。

score 0 · Accepted Answer

void recursiveReverse(struct node** head_ref) { struct node* first; struct node* rest;

/* empty list */
if (*head_ref == NULL)
   return;  

/* suppose first = {1, 2, 3}, rest = {2, 3} */
first = *head_ref; 
rest  = first->next;

/* List has only one node */
if (rest == NULL)
   return;  

/* reverse the rest list and put the first element at the end */
recursiveReverse(&rest);
first->next->next  = first; 

/* tricky step -- see the diagram */
first->next  = NULL;         

/* fix the head pointer */
*head_ref = rest;

}

説明

ここで、ポインター first と next は、各内部呼び出しに対してローカルです。スタックでは、関数呼び出しごとに、スタック上に作成された 2 つの一時ポインターが自身を呼び出すようになりました。*first はリンクリストの先頭要素であり、*rest はリンクリストの次の要素へのポインターです。各呼び出しで net が再帰に渡されるということは、2 番目の要素ポインタが渡されることを意味します。(rest == NULL)スタックの巻き戻しが開始された場合、スタックの巻き戻しが発生した場合、最後に要素が残っていない場合。スタックの巻き戻しでは、*rest forward は低レベルの *first ポインターを指します。これは、巻き戻し中にあるスタックから別のスタックにポインターを単純に反転させます。最初に *first が最後の要素になるため、不正な参照を防ぐために次の要素が null に変更されますfirst->next = NULL

list - 単一リンクリストを再帰的に逆にする

5 に答える 5

Related

Reference