反向遞歸鏈表 - 不同的函數簽名

存在與可能與同樣的問題很多帖子，但問題說，它必須由反向遞歸鏈表 - 不同的函數簽名

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

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

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

完成三個空格必須填寫前兩個是根本

return NULL

和

return lh

repectivel y

一種方法可能只是倒下並倒轉指針，但在那種情況下，即使在回溯後我怎樣才能保持尾部完好無損？有沒有可能？

來源

2011-12-12 Aseem Dua

訣竅解決遞歸問題是假裝你已經完成。要自己解決這個作業，您需要回答三個問題：

如何反轉空列表？（即lh設置爲NULL的列表）？
你如何反轉一個列表只有一個項目？
如果有人可以將列表中除初始列表以外的所有項目都轉換回來，那麼您將第一個項目從最初列表添加到列表中預先反轉的「尾部」部分？

你已經回答了前兩個：NULL和lh是正確的答案。現在想第三個的：

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-12 17:02:32 dasblinkenlight

真的很不錯的答案！清楚，完整，並給出理由。 –

@PeteWilson謝謝！ – dasblinkenlight

這實際上不是一個家庭作業問題，而是一個前一年的sem結束測試文件..你是否意味着要做這樣的事情？ tail = reverse（lh-> next）; lh-> next = NULL; return tail; 我沒有得到我們想要做什麼 –

下面是一個API，它做了單鏈表的逆轉，這一個最好的算法中的，我已經看到：

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-12 17:02:20 PKS

我覺得這個回答是：

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-12 17:38:48 NicolasP

反向遞歸鏈表 - 不同的函數簽名

回答

相關問題