已超出LinkedList內存限制

」給定一個鏈表和一個值x，對它進行分區，使得所有小於x的節點在節點大於或等於x之前出現您應該保留兩個分區中每個節點的原始相對順序「。

我的問題是，爲什麼我們必須有「right.next = null」這一行。爲什麼它會給出「內存限制超出錯誤」，如果我不把一個NULL放到LinkedList的末尾？在此先感謝！

public ListNode partition (ListNode head, int x) { 
     if (head==null) return head; 
     ListNode leftDummy = new ListNode(0); 
     ListNode rightDummy = new ListNode(0); 
     ListNode left = leftDummy; 
     ListNode right = rightDummy; 

     while (head!=null) { 
      if (head.val < x) { 
       left.next = head; 
       left = head; 
      } else { 
       right.next = head; 
       right = head; 
      } 
      head = head.next; 
     } 
     // merge the two 
     right.next = null;  // WHY THIS LINE?? 
     left.next = rightDummy.next; 
     return leftDummy.next; 
    }

來源

2016-11-07 Emile

如果沒有像你這樣分區的原始列表，所以我的猜測是當你合併它們時，你正在創建N^2節點的數量。這是使用調試器可以幫助解釋你做得更好的地方。 –

那麼，你有兩個指針，左右兩個，你正在構建分區。它們總是指向相應分區的最後一個元素。 leftDummy和rightDummy是這些分區的開始。那麼，你到底應該向左分區的最後一個元素連接到正確的的第一個元素：

left.next = rightDummy.next;

如果用來指向一些其他的元素在原正確的分區的最後一個元素列表中，你應該糾正，否則你可以得到一個無限循環：

right.next = null;

下面是一個例子：

列表：1 - > 5 - > 8 - > 2 將x = 4，在最後你得到兩個分區：

leftDummy = 1 -> 2 = left 
rightDummy = 5 -> 8 = right

但是在原始列表中，包含8（現在稱爲右）的元素指向2，所以如果試圖遍歷新列表1 - > 2 - > 5 - > 8，實際上會得到：

1 -> 2 -> 5 -> 8 -> 2 -> 5 -> 8 -> 2.....

因此，您必須刪除對右側變量中「next」元素的引用。

來源

2016-11-07 20:36:24 Igor

已超出LinkedList內存限制

回答

相關問題