遞歸反向單鏈表

我想只寫一個基本函數來反轉一個遞歸的單鏈表。我想知道我是否以正確的方式解決了這個問題？也許有人可以給我一些指點。遞歸反向單鏈表

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; 
}

來源

2012-10-25 mystycs

當你運行你的代碼時會發生什麼？ –

您的代碼中出現一些看似錯誤。 Node *＆p應該只是Node * p。另外我懷疑你的任務p-> next-> next = p。基本上你現在應該指向前一個和前一個應該指向當前。在此之前，您應該保存下一個指針以便在列表中進一步前進 – fayyazkl

這不是最有效的方式，但要做到這一點，你可以調用的「下一個」指針反向方法，直到沒有下存在。一旦出現，請設置在前一個旁邊。從遞歸返回後，設置旁邊的前一個。例如，請參閱recursive version here。從鏈接：

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-25 05:04:36 user1118321

OP提到了「遞歸」的意思，並且您說「非遞歸」。不完全響應。 –

噢，把它倒在我腦袋裏。我馬上糾正一下。 – user1118321

遞歸解決方案可以看起來很漂亮，即使在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-25 05:29:35 rici

這是你所需要的：

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-25 05:56:26 ozox

這可能是有益的

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-04 20:09:34

您可以編輯和合並這兩個答案。您也可以花時間解釋爲什麼會出現這個問題 – jean

如何合併這2條評論。我是新來的，所以我對這個網站知之甚少。關於解釋：由於此代碼遞歸地反轉單鏈表，我認爲這將有所幫助。 –

thnx爲合併想法..現在我知道如何做到這一點 –

linkedList *reverseMyNextPointer(linkedList *prevNode,linkedList *currNode) 
{ 
    linkedList *tempPtr; 
    if(currNode == NULL) 
    { 
     return prevNode; 
    } 
    else 
    { 
     tempPtr = currNode->next; 
     currNode->next = prevNode; 
     return reverseMyNext(currNode,tempPtr); 
    } 
} 

head = reverseMyNextPointer(NULL,head);

來源

2016-06-07 15:45:54

這裏是保存收益的解決方案價值爲無效。

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-30 01:51:49

遞歸反向單鏈表

回答

相關問題