K-й элемент с конца списка

Решение

Задача требует найти K-й элемент с конца в односвязном списке. Это классическая задача, которая демонстрирует работу с указателями и требует выбора между пространством и временем.

Определение структуры узла

class ListNode:
    """Класс для представления узла односвязного списка."""
    def __init__(self, value: int):
        self.value = value
        self.next = None

Решение 1: Двухпроходный алгоритм (Оптимально)

Первый проход определяет длину списка, второй проход находит нужный элемент.

def find_kth_from_end_two_pass(head: ListNode, k: int) -> ListNode:
    """
    Находит K-й элемент с конца в двухпроходном алгоритме.
    
    Args:
        head: Голова списка
        k: Позиция с конца (1-индексирована)
    
    Returns:
        K-й элемент с конца, или None если не существует
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    # Первый проход: определяем длину списка
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    
    # Проверяем корректность k
    if k > length or k <= 0:
        return None
    
    # Второй проход: находим элемент на позиции (length - k)
    target_position = length - k
    current = head
    
    for _ in range(target_position):
        current = current.next
    
    return current

Решение 2: Техника двух указателей (Two-Pointer Technique)

Один указатель движется впередна K позиций, затем оба движутся вместе до конца.

def find_kth_from_end_two_pointer(head: ListNode, k: int) -> ListNode:
    """
    Находит K-й элемент с конца используя два указателя.
    Однопроходный алгоритм.
    
    Args:
        head: Голова списка
        k: Позиция с конца (1-индексирована)
    
    Returns:
        K-й элемент с конца, или None если не существует
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    # Создаём фиктивный узел для обработки граничного случая (удаление head)
    dummy = ListNode(0)
    dummy.next = head
    
    first = dummy
    second = dummy
    
    # Перемещаем first на k+1 позиций вперёд
    for _ in range(k + 1):
        if first is None:
            return None  # k больше чем длина списка
        first = first.next
    
    # Перемещаем оба указателя до конца
    while first:
        first = first.next
        second = second.next
    
    return second.next

Решение 3: Рекурсивный подход

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

def find_kth_from_end_recursive(head: ListNode, k: int) -> ListNode:
    """
    Находит K-й элемент с конца используя рекурсию.
    
    Args:
        head: Голова списка
        k: Позиция с конца
    
    Returns:
        K-й элемент с конца, или None если не существует
    
    Time Complexity: O(n)
    Space Complexity: O(n) из-за стека вызовов
    """
    def helper(node: ListNode, k: list[int]) -> ListNode:
        if node is None:
            return None
        
        result = helper(node.next, k)
        k[0] -= 1
        
        # Когда счётчик достигает 0, мы нашли K-й с конца
        if k[0] == 0:
            return node
        
        return result
    
    # Используем список для сохранения счётчика (изменяемый объект)
    counter = [k]
    return helper(head, counter)

Примеры использования

# Создаём тестовый список: 1 -> 2 -> 3 -> 4 -> 5
def create_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

def list_to_string(node):
    result = []
    while node:
        result.append(str(node.value))
        node = node.next
    return " -> ".join(result)

# Тест
head = create_list([1, 2, 3, 4, 5])
print(f"Список: {list_to_string(head)}")

# K = 2
result = find_kth_from_end_two_pointer(head, 2)
print(f"2-й элемент с конца: {result.value}")  # 4

# K = 1 (последний элемент)
result = find_kth_from_end_two_pointer(head, 1)
print(f"1-й элемент с конца: {result.value}")  # 5

# K = 5 (первый элемент)
result = find_kth_from_end_two_pointer(head, 5)
print(f"5-й элемент с конца: {result.value}")  # 1

Анализ подходов

Граничные случаи

# 1. K больше чем размер списка
find_kth_from_end_two_pointer(head, 100)  # None

# 2. K = 1 (последний элемент)
find_kth_from_end_two_pointer(head, 1)  # 5

# 3. K = длина (первый элемент)
find_kth_from_end_two_pointer(head, 5)  # 1

# 4. Один элемент в списке
single = ListNode(42)
find_kth_from_end_two_pointer(single, 1)  # 42

# 5. Пустой список
find_kth_from_end_two_pointer(None, 1)  # None

Для QA автоматизации

Рекомендуется решение Two-Pointer (Решение 2), так как оно:

• Проходит список только один раз (O(n))
• Использует O(1) дополнительной памяти
• Корректно обрабатывает граничные случаи
• Часто используется в реальных системах