2

再帰的な単一リンクリストを逆にする基本的な関数を書こうとしています。正しいアプローチでこれに取り組んだかどうか疑問に思っていましたか？多分誰かが私にいくつかの指針を与えることができます。

 void reverse(Node*& p) {
  if (!p) return;
  Node* rest = p->next;
  if (!rest) return;
  reverse(rest);
  p->next->next = p;
  p->next = NULL;
  p = rest;
}
4

6 に答える 6

7

これは最も効率的な方法ではありませんが、それを行うには、次がなくなるまで、「次の」ポインターを使用して逆メソッドを呼び出すことができます。そこに来たら、次を前に設定します。再帰から戻った後、次を前に設定します。例については、こちらの再帰バージョンを参照してください。リンクから：

Node * reverse( Node * ptr , Node * previous)
{
    Node * temp;
    if(ptr->next == NULL) {
        ptr->next = previous;
        previous->next = NULL;
        return ptr;
    } else {
        temp = reverse(ptr->next, ptr);
        ptr->next = previous;
        return temp;
    }
}
reversedHead = reverse(head, NULL);
于 2012-10-25T05:04:36.950 に答える
4

これは役に立つかもしれません

List
{
public:

    .....

    void plzReverse()
    {
         Node* node = myReverse(head);
         node->next = NULL;
    }

private:

    Node * myReverse(Node * node)
    {
        if(node->next == NULL)
        {
            head = node;
            return node;
        }
        else
        {
            Node * temp = myReverse(node->next);
            temp ->next = node;
            return node;
        }
     }
}

別の解決策は次のとおりです。

List
{
public:
.....

    void plzReverse()
    {
        Node* node = myReverse(head, head);
        node->next = NULL;
    }

private:

    Node * myReverse(Node * node, Node*& rhead)
    {
        if(node->next == NULL)
        {
            rhead = node;
            return node;
        }
        else
        {
            Node * temp = myReverse(node->next,rhead);
            temp ->next = node;
            return node;
        }
     }
}
于 2015-03-04T20:09:34.333 に答える
2

これはあなたが必要とするものです：

Node* reverse(Node* p) {
  if (p->next == NULL) {
    return p;
  } else {
    Node* t = reverse(p->next); // Now p->next is reversed, t is the new head.
    p->next->next = p; // p->next is the current tail, so p becomes the new tail.
    p->next = NULL;
    return t;
  }
}
于 2012-10-25T05:56:26.960 に答える
1

再帰的なソリューションは、C++ であっても非常にきれいに見えます。

Node* reverse(Node* pivot, Node* backward = 0) {
  if (pivot == 0)  // We're done
    return backward; 
  // flip the head of pivot from forward to backward
  Node* rest = pivot->next;
  pivot->next = backward;
  // and continue
  return reverse(rest, pivot);
}

ほとんどの C++ コンパイラは末尾呼び出しの最適化を行うため、これが反復ソリューションよりも効率が悪いと考える理由はありません。

于 2012-10-25T05:29:35.383 に答える
0 
linkedList *reverseMyNextPointer(linkedList *prevNode, linkedList *currNode)
{
    linkedList *tempPtr;
    if(!currNode)
        return prevNode; 
    else
    {
        tempPtr = currNode->next;
        currNode->next = prevNode;
        return reverseMyNext(currNode,tempPtr);
    }
}

head = reverseMyNextPointer(nullptr,head);
于 2016-06-07T15:45:54.183 に答える
0

戻り値を void として保持するソリューションを次に示します。 

void reverse(Node*& p) {
  if (!p) return;
  Node* rest = p->next;
  if (!rest) {
      rest = p;
      return;
  }
  reverse(rest);
  p->next->next = p;
  p->next = NULL;
  p = rest;
}
于 2016-11-30T01:51:49.753 に答える