Зачем нарушать связь между двумя узлами списка при разбиении списка?

Question

Я пытался решить проблему Partition List на LeetCode. Проблема заключается в сортировке связанного списка с узлом целевого списка, так что все узлы списка, имеющие меньшее значение, чем целевое, будут поступать до цели, тогда как их первоначальный относительный порядок остается неизменным.

Я смог составить простой алгоритм и передать онлайн-судье, в основном создавая два указателя и используя их каждый, чтобы связать либо узлы < цели, либо >= цель при перемещении по списку.

public ListNode partition(ListNode head, int x) { 
    ListNode ptr = head; 
    ListNode small = new ListNode(0); 
    ListNode big = new ListNode(0); 
    ListNode dummy_1 = big; 
    ListNode dummy_2 = small; 
    int i = 1; 
    while (ptr != null) { 
     if (ptr.val < x) { 
      small.next = ptr; 
      small = small.next; 
     } else { 
      big.next = ptr; 
      big = big.next; 
     } 
     ListNode help = ptr.next; 
     ptr.next = null; 
     ptr = help; 
    } 
    small.next = dummy_1.next; 
    return dummy_2.next; 
} 

следующие коды разрывает связь между ptr и ptr.next, и переместить
ptr к первоначальному ptr.next.

ListNode help = ptr.next; 
ptr.next = null; 
ptr = help; 

То, что я не совсем понял, еще в том, что, почему этот шаг необходим, так как мы можем двигаться ptr его next и непосредственно обновить ссылку позже, используя small.next = ptr и big.next = ptr в то время как петли;

Однако, когда я просто использовал ptr = ptr.next вместо трех строк кода выше, онлайн-судья ответил с ошибкой Memory Limit Exceeded.

Я был бы очень признателен, если кто-нибудь сможет это объяснить. Что может вызвать ошибку ограничения памяти, поскольку, как представляется, уже избегается какой-либо циклический список?

Answer 1

Как прокомментировал, просто установив big.next = нуль работает (я управлял этим с помощью NetBeans/Java).

static ListNode partition(ListNode head, int x) { 
    ListNode ptr = head; 
    ListNode small = new ListNode(0); 
    ListNode big = new ListNode(0); 
    ListNode dummy_1 = big; 
    ListNode dummy_2 = small; 
    while (ptr != null) { 
     if (ptr.val < x) { 
      small.next = ptr; 
      small = small.next; 
     } else { 
      big.next = ptr; 
      big = big.next; 
     } 
     ptr = ptr.next; 
    } 
    small.next = dummy_1.next; 
    big.next = null; 
    return dummy_2.next; 
} 

Answer 2

Объект не будет иметь права на сбор мусора, если на него указана хотя бы одна ссылка.Вы можете следить this пост, чтобы построить краткое понимание вокруг этой концепции

Вот что происходит в обоих случаях

Случай 1:

ptr = ptr.next 

Предположим Linked List находится в следующем состоянии в течение первых итерация

продвигается, но предыдущий узел, имеющий значение 7 по-прежнему ссылается head

ptr является передовой, но предыдущий узел, имеющий значение 1 по-прежнему ссылается его предыдущего узла

ptr продвигается, но предыдущий узел, имеющий значение 3 по-прежнему ссылается на его предыдущий узел

И это продолжается до конца цикла. Если список имеет очень большой размер, тогда память не восстанавливается. Как ваш судья сказал, это может привести к ошибке, как Memory Limit Exceeded

Случай 2:

ListNode help = ptr.next; 
    ptr.next = null; 
    ptr = help; 

Предположим, Связанный список находится в следующем состоянии во время первой итерации.

• help указывает на следующий узел указываемые ptr
• ptr является повторно ссылается, чтобы указать на help, на следующей стадии
• Следовательно, узел ранее, на который указывает ptr (тот, который имел значение 7) имеет право на сбор мусора
• И память исправлена ​​

• help указывает на следующий узел указываемые ptr
• ptr является повторно ссылается, чтобы указать на help, на следующей стадии
• Следовательно, узел ранее, на который указывает ptr (один из которых имеет значение 1) имеет право на сбор мусора
• И память регенерируется

• help указывает на следующий узел, на который указывает ptr
• ptr повторно ссылки, чтобы указать на help, в следующем шаге
• Следовательно узел ранее указывал на ptr (тот, который имел значение 3) имеет право на Garbage Collection
• И память регенерируется

• help указывает на следующий узел, на который указывает ptr
• ptr повторно ссылается, чтобы указать на help, в следующем step
• Следовательно, узел, на который раньше указывал ptr (тот, который имел значение 2) имеет право на Garbage Collection
• И память регенерируется