LinkedListのメモリ制限を超えました

Question

問題はLeetcodeからです。

"リンクリストと値xを指定すると、xより小さいすべてのノードがx以上のノードより前に来るようにパーティションを分割します。 2つのパーティションのそれぞれのノードの元の相対順序を保持する必要があります"

私の質問は、なぜ "right.next = null"という行が必要なのかです。 LinkedListの最後にNULLを置かないと、なぜ "メモリ制限を超えたエラー"が出るのですか？ ありがとうございます！

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; 
    } 

Answer 1

まあ、パーティションを構築する際に左右に2つのポインタがあります。それらは常にそれぞれのパーティションの最後の要素を指します。 leftDummyとrightDummyは、それらのパーティションの始まりです。だから、最後に、あなたは、右のいずれかの最初の要素を左パーティションの最後の要素を添付する必要があります

left.next = rightDummy.next; 

と右のパーティションの最後の要素は、オリジナルで他のいくつかの要素を指すために使用された場合リスト、あなたはそうしないと、無限ループを得ることができ、それを修正する必要があります。ここでは

right.next = null; 

は例です：

あなたのリストは：1 - > 5 - > 8 - X = 4で> 2 、中最後に2つのパーティションを取得します。

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

しかし、元のリストには、（今と呼ばれる）8を含む要素は、2指さ、あなたは1新しいリストを反復処理しようとするので、もし - > 2 - > 5 - > 8、あなたが実際に取得します：

したがって、正しい変数の「次の」要素への参照を削除する必要があります。