Превышен лимит памяти LinkedList

Question

Проблема с Leetcode.

«Учитывая связанный список и значение 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; 
    } 

Answer 1

Ну, у вас есть два указателя слева и справа, с которыми вы строите разделы. Они всегда указывают на последний элемент соответствующего раздела. leftDummy и rightDummy - это начало этих разделов. Так, в конце концов, вы должны прикрепить последний элемент левого раздела на первый элемент правой:

left.next = rightDummy.next; 

И если последний элемент нужного раздела используется, чтобы указать на какой-либо другой элемент в оригинале список, вы должны исправить то, что, в противном случае вы можете получить бесконечный цикл:

right.next = null; 

Вот пример:

Ваш список: 1 -> 5 -> 8 -> 2 при х = 4, в в конце вы получаете два раздела:

Но в исходном списке элемент, содержащий 8 (теперь называемый справа), указывает на 2, поэтому, если вы попытаетесь перебрать новый список 1 -> 2 -> 5 -> 8, вы получите:

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

Итак, вы должны удалить ссылку на «следующий» элемент в правой переменной.