迭代式地複製鏈接列表

這是一項家庭作業。將以下遞歸深度複製方法更改爲迭代等效方法。我走近了，需要你的幫助才能把它做好。遞歸執行：迭代式地複製鏈接列表

public static StringNode copy(StringNode str) { 
     if (str == null) 
      return null; 

     StringNode copyFirst = new StringNode(str.ch, null); 
     copyFirst.next = copy(str.next); 
     return copyFirst; 
    }

這裏是什麼我趕上了，迭代等同。已經實現了static length()方法來返回給定鏈接列表中有多少個節點。

public static StringNode copy(StringNode str) { 
    if (str == null) 
     return null; 

    StringNode firstNode = new StringNode(str.ch ,null); 
    StringNode prevNode = firstNode; 
    StringNode nextNode; 

    for (int i = 1; i < length(str); i++) { 
     nextNode = new StringNode(str.next.ch, null); 
     prevNode.next = nextNode; 
     prevNode = nextNode; 
    } 

    return firstNode; 
}

問題：測試我的實現，我創建了一個鏈表str1與字符值，'n', 'b', 'a'，然後調用

StringNode copy = StringNode.copy(str1);

然後我刪除str1中的最後一個節點，把它作爲'n','b', 但是，當我嘗試打印出存儲在副本中的內容時，我獲得了 'n', 'b', 'b'而不是'n', 'b', 'a'。

有什麼建議嗎？

來源

2012-11-06 Hank

您還需要在您的循環中向前移動str，否則您會在每次迭代中不斷在list中添加same str。第一次調用方法的第一個元素是不同的。然後str.next通過你的循環是一樣的。

所以，你需要在你的for循環添加以下代碼： -

str = str.next;

此外，你的循環有一定的問題。你不應該迭代到length(str)。但直到str == null。

所以，最後你的循環應該是這樣的： -

while (str.next != null) { // Iterate till str.next != null, as we are creating 
          // the next node in the loop for current node str 

    nextNode = new StringNode(str.next.ch, null); 
    prevNode.next = nextNode; 
    prevNode = nextNode; 

    str = str.next; // Move to next node. 
}

while循環在這種情況下使用，因爲你不知道應該循環多少次迭代。

來源

2012-11-06 06:58:22

謝謝Rohit。這樣可行。我的兩個疏忽，1）我忘記遍歷參考str到下一個節點。 2）str的長度應該在循環的外部計算，因爲str引用被改變爲循環內的下一個節點。 – Hank

@HangYu ..不，不要使用'for-loop'。你不應該使用'length'來迭代。相反，直到你得到一個'null' str。檢查我更新的帖子。 –

謝謝Rohit。實際上，在我的測試中，上面的while循環經歷了一個空指針異常，因爲我在while循環之外創建了'firstNode'。因此它應該是'while（str.next！= null）{...}' – Hank

迭代式地複製鏈接列表

回答

相關問題