這是我想出的用于在 Java 中反轉單鏈表的代碼，我想知道它是否正確完成。我知道它的作業原理和運行時間為 O(n)，但這是正確的方法還是可以改進的方法？另外，在反轉長鏈表（不使用迭代替代方案）時，我可以做些什么來避免堆疊溢位問題，因為當嘗試反轉大小大于 8300 的鏈表時，它會導致堆疊溢位例外。
private void reverse(Node node) {
if(node != this.tail) {
reverse(node.next);
this.tail.next = new Node(node.item);
this.tail = this.tail.next;
this.head = this.head.next;
}
}
public void reverse() {
reverse(this.head);
}
uj5u.com熱心網友回復：
該解決方案似乎很好，但是您不需要Node使用舊物件的值創建新Node物件。O(n)您可以就地和時間復雜度反轉單鏈表。
public Node reverse(Node head) {
Node prev = null;
while(head!= null) {
Node rem = head.next;
head.next = prev;
prev = current;
current = rem;
}
return prev; // prev is the new head of your linked list
}
如果您不想使用迭代解決方案（盡管我建議這樣做），您可以使用下面的遞回解決方案：
public Node reverseList(Node node) { // send the head of the list
if(current == null) return null;
reverse(current);
return this.tail; // now tail is the head and head is the tail
}
public Node reverse(Node node) {
if(node.next == null) {
this.tail = node;
} else {
reverse(node.next).next = node;
node.next = null;
}
return node;
}
我沒有關于您的鏈接串列的足夠詳細資訊，但我假設您有this.head和this.tail欄位。即使this.tail未初始化，此解決方案也有效。而且，如果是預先賦值的，就不需要從頭開始遍歷鏈表。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/435770.html
上一篇：' '操作不適用于型別function(x:real)：real和real。檢查程式的運行情況a=0.1;b=1.0；h=0.1;
下一篇：想知道演算法的時間復雜度