倒車鏈表遞歸

的問題是，我需要寫一個遞歸算法反轉單鏈表L，從而使節點的順序變得相反。它似乎有點抽象，但我不需要代碼或任何東西，因爲問題請求算法，我有點卡住了。我不知道開始，我的意思是我有一些簡單的事情要做鏈接列表，如添加到前面和刪除，但倒退（尤其是遞歸）看起來像一堵牆。倒車鏈表遞歸

來源

2012-03-16 serge

這是一個類似的問題（單擊鏈接列表的內容反向打印）：http://stackoverflow.com/questions/9706681/recursive-printing-of-a-singly-linked-list-homework/9706802 ＃9706802這應該指出你在正確的方向。在所有人都開始跑步之前，請提供一個提示，試着解釋你在發佈時嘗試過的內容，而不是先來到這裏。 – jzworkman 2012-03-16 15:14:36

你嘗試了什麼？你究竟在「卡住」了什麼？向我們展示您的初步嘗試[即使未完成]，以便我們可以指導您如何解決您的問題，並且仍然從過程中學習。 – amit 2012-03-16 15:15:05

你應該做的第一件事是用簡單的句子來描述你將如何反轉鏈表。如果你能夠清楚地識別出反轉鏈表所需的步驟，那麼寫一些代碼應該不會很困難。當你完成後，嘗試編寫一個遞歸函數來反轉鏈表（順便說一下，不要認爲算法是複雜的，它可能是一個非常簡單的函數）。 – Kiril 2012-03-16 15:16:09

因爲你並不需要提供特定的代碼，我會做你的功課，如果我甚至給你僞代碼，所以我只給你一些提示;-)

的一般方法將是做

蓋的基本情況（如果給定的列表爲空，則返回空列表）
遞歸和扭轉尾
頭追加到反轉的尾巴。

爲了扭轉1 -> 2 -> 3它會去像

reverse(1 -> 2 -> 3) 
= reverse(2 -> 3) -> 1 
= reverse(3) -> 2 -> 1 
= reverse() -> 3 -> 2 -> 1 
= emptyList -> 3 -> 2 -> 1 
= 3 -> 2 -> 1

來源

2012-03-16 15:14:07 aioobe

好吧，我得到步驟1和3.如何進一步打破步驟2，特別是「反向尾巴」部分？ – serge 2012-03-16 15:17:47

遞歸調用尾部只是對'reverse'進行遞歸調用。它可能看起來像'reverse（currentHead.next）'。 – aioobe 2012-03-16 15:19:11

考慮兩個節點列表的簡單情況：A-> B-> NULL。你如何假設你可以反轉該列表，使其成爲B-> A-> NULL？

如果仍然不能得到它，想象積木堆是一個鏈表。通過斷開和重新連接樂託來執行現實生活中的重新排序，並記下您執行的每一步。

來源

2012-07-16 03:27:19

讓我們定義的方法reverse(L, n)可逆轉L中的第一個n ≤ L.size()節點，只是以L (end = null if n = L.size())第n個節點。如果L.size() ≤ 1我們在完成後返回一個指向結束節點，讓我們假設L具有至少2節點。如果n = 1那麼我們返回L.first().next()否則，我們遞歸地調用reverse(L, n - 1)並讓結束表示返回的指針指向L中的第n個節點。然後我們將ret設置爲end.next()，如果是n < L.size()，則返回null。然後我們將L指向的節點插入到L的前面，然後返回ret。

只是供參考，總運行時間爲O（n）。

來源

2017-01-18 23:17:55 sunny

倒車鏈表遞歸

回答

相關問題