Решение задачи #19. Python LeetCode, Remove nth node from end of list

Задача на алгоритм для работы со связным списком в Python. Требуется удалить N-й узел с конца односвязного списка, сохранив структуру данных. Задача проверяет умение эффективно манипулировать связными списками с использованием алгоритма двух указателей (fast and slow), который решает проблему за один проход без дополнительной памяти.

Вариант решения задачи на Python с LeetCode

Категория: Алгоритмы.
Название задачи: Remove nth node from end of list.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Given the head of a linked list, remove the nth node from the end of the list and return its head.

Решение:

Python

# Определение узла связного списка
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        # Создаем фиктивный узел, чтобы упростить удаление первого элемента
        dummy = ListNode(0)
        dummy.next = head
        
        # Инициализируем два указателя: fast и slow
        fast = dummy
        slow = dummy
        
        # Перемещаем fast на n узлов вперед
        for _ in range(n + 1):
            fast = fast.next
        
        # Перемещаем fast до конца списка, slow будет отставать на n узлов
        while fast is not None:
            slow = slow.next
            fast = fast.next
        
        # Удаляем n-й узел с конца
        slow.next = slow.next.next
        
        # Возвращаем новый head списка (исключая фиктивный узел)
        return dummy.next

Объяснение кода

Фиктивный узел (dummy):
Используется для упрощения обработки случая, когда нужно удалить первый элемент списка.
dummy.next указывает на head списка.

Два указателя (fast и slow):
fast сначала перемещается на n + 1 шагов вперед, чтобы между fast и slow образовался разрыв в n узлов.
Затем оба указателя двигаются вместе, пока fast не достигнет конца списка.
В этот момент slow окажется перед узлом, который нужно удалить.

Удаление узла:
Когда slow находится перед n-м узлом с конца, мы просто перебрасываем ссылку slow.next через удаляемый узел (slow.next = slow.next.next).
Это исключает узел из списка.

Возврат результата:
Возвращаем dummy.next, так как head мог измениться (если удалялся первый элемент).

Пример работы:
head =
[1,2,3,4,5]

n =
2

Output
[1,2,3,5]

Expected
[1,2,3,5]

Мы рассмотрели пример решения, который был принят и засчитан платформой как правильный, но вы можете найти свой способ решения задачи, возможно лучше.

Источник решения: hdhai.com