Удалить n-й узел из конца списка [LeetCode]

Question

Вопрос очень простой, и алгоритм у меня тоже есть. Единственное, чего я не понимаю, - это утверждение return. зачем нам возвращать dummy.next, если мы вообще не внесли никаких изменений в dummy.

Думаю, мой вопрос в том, когда мы изначально устанавливаем slow и fast равными dummy , разве мы не просто делаем глубокую копию списка / манекена (это означает, что любое изменение, которое мы внесли в любой из них, не влияет на манекен), или я что-то упускаю ..?

* 1009 . Если вы можете подкрепить свое объяснение примером, было бы здорово.

А вот ссылка на вопрос: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
         
        ListNode slow = dummy, fast = dummy;
        
        for(int i = 0; i <= n ; i++){
            fast = fast.next;
        }
        
        while(fast != null){
          fast = fast.next;
          slow = slow.next;
        }
        
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

Answer 1

Единственное различие, которое я вижу между использованием манекена и неиспользованием, заключается в том, что необходимо удалить первый элемент в списке. В этом случае без использования манекена не удастся удалить головной узел. Тем не менее, это можно легко исправить, добавив простую проверку во время начального l oop.

Вот мое решение без использования фиктивной головы.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode slow = head, fast = head;
        
    for(int i = 0; i <= n ; i++){
        if (fast == null) {
            return head.next;
        }
        fast = fast.next;
    }
        
    while(fast != null){
      fast = fast.next;
      slow = slow.next;
    }
        
    slow.next = slow.next.next;
        
    return head;
}

Чтобы ответить ваши другие вопросы,

разве мы не просто углубляемся в список / фиктивный

глубокого копирования не происходит, так как макет хранит ссылку на голова, а не копия.

зачем нам возвращать dummy.next, если мы вообще не внесли никаких изменений в dummy.

манекен определен быть перед головой. поэтому, когда мы хотим вернуть измененную голову, мы возвращаем следующий узел после пустышки. Если бы мы просто вернули пустышку, то перед ответом, который мы получили бы, было бы лишнее 0, которое нам не нужно.

Answer 2

Чтобы ответить на ваши вопросы,

, когда мы изначально устанавливаем slow и fast равными dummy, разве мы не просто делаем глубокий список / dummy

Нет, это не так. Назначение осуществляется по ссылке, поскольку ListNode является ссылочным типом. Таким образом, изменение любого из фиктивных, медленных и быстрых значений покажет его влияние на все три переменные.

единственное, чего я не понимаю, - это оператор return. зачем нам return dummy.next

Что касается оператора return, нам все равно нужно вернуть начало списка, которое было предоставлено нам в качестве параметра head в функции, на которую указывает by dummy.next

Что касается того, почему операции непосредственно не выполняются на head и нужна фиктивная переменная и шаги

ListNode dummy = new ListNode(0);
dummy.next = head;

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