鏈表的遞歸

當給定一個整數數組時，我試圖用它之前的整數乘積來更改每個元素。鏈表的遞歸

例如，int[] array = {2,2,3,4};現在是：{2, 4, 12, 48};

我添加的每個元素爲LinkedList，我試圖以遞歸方式做到這一點。

這是我有：

Node curr = list.getFirst(); 
product(curr); 

public static void product(Node curr) 
{ 
    if(curr == null) 
    { 
     return; 
    } 
    else 
    { 
     int data = curr.getData() * curr.getNext().getData(); 
     Node newNode = new Node(data); 
     curr.setNext(newNode); 

     // product(curr); 
    } 
}

的第一款產品的工作原理：{2,4}，但是當我試圖把在遞歸，我得到一個計算器。有什麼建議麼？？

編輯：所以我要麼得到一個計算器或空指針異常是因爲我更新的列表，然後試圖讓下一個整數（但原因，因爲這裏只有兩個元素該列表中沒有getNext()）。我不知道如何解決這個問題。

來源

2015-06-23 kris

的部分這個問題似乎是你添加下一個節點，所以每次你遞歸下一個節點，因此沒有結束遞歸。不知道爲什麼Tims解決方案沒有解決這個問題。 –

@BenKnoble我在原來的帖子中不小心把他的舊程序留在了一行，儘管我已經刪除了它。也許他運行了這個舊版本的代碼。 –

@TimBiegeleisen這是非常可能的。 –

它看起來像你在遞歸中有點束縛。我修改了您的方法以接受Node以及上一次迭代的產品。在迭代的每一步中，我都更新已存在的List中的值，因此不需要使用new運算符。

public static void product(Node curr, int value) { 
    if (curr == null) { 
     return; 
    } 
    else { 
     int data = value * curr.getData(); // compute current product 
     curr.setData(data);     // update Node 
     product(curr.getNext(), data);  // make recursive call 
    } 
}

來源

2015-06-23 01:43:57

你從哪裏得到'newNode'？ – Gosu

對不起，我在移動設備上，忘記刪除舊代碼。 –

謝謝蒂姆！雖然我仍然得到這個代碼的堆棧溢出。 – kris

這是因爲你在當前節點上調用遞歸方法，所以它實際上永遠不會在LinkedList中向前移動。您可以簡單地更新下一個節點的數據並對其調用遞歸方法。請參閱下面的代碼：

Node curr = list.getFirst(); 
product(curr); 

public static void product(Node curr) 
{ 
    Node next = curr.getNext(); 
    if(next == null) 
    { 
     return; 
    } 
    else 
    { 
     int data = curr.getData() * next.getData(); 
     next.setData(data); 
     product(next); 
    } 
}

來源

2015-06-23 01:47:24

不幸的是，這給了我一個空指針異常，我認爲是因爲我們不知道curr是否具有getNext，這可能是爲什麼我的原始代碼不起作用r – kris

是的，你是對的，下一個可以是null，所以我們應該返回當下一個爲空時。請參閱更新的代碼。 –

實際上有兩個問題的代碼。

遞歸永遠不會結束，即，它實際上不是移動到一個更小的「子問題」作爲遞歸再次調用同一節點和試。

創建新節點並修改下一個節點後，我們還需要將節點「連接」下一個節點，否則鏈接將丟失。請檢查以下解決這兩個問題的方法。

雖然我沒有做到這一點正在爲簡單的數據集的過度測試。原版： 2-> 4-> 5-> 6-> 8->空倍增列表： 2-> 8-> 40-> 240-> 1920->空

public void product(Node curr) { 
    if (curr.getNext() == null) { 
     return; 
    } else { 
     int data = curr.getData() * curr.getNext().getData(); 
     Node newNode = new Node(); 
     newNode.setData(data); 
     Node nodeAfterNextNode = curr.getNext().getNext(); 
     newNode.setNext(nodeAfterNextNode); 
     curr.setNext(newNode); 

     product(newNode); 
    } 
}

來源

2015-06-23 02:20:21 Sambaran

回答

相關問題