Базовое определение узла списка

class ListNode:
    """Узел односвязного списка"""
    def __init__(self, val=0, next=None):
        self.val = val    # Значение узла
        self.next = next  # Ссылка на следующий узел

---

Задача 1: Обход связанного списка

Описание задачи

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

Принципы решения

• Итеративный подход: использование указателя, который последовательно перемещается по списку
• Цикл while: продолжать пока указатель не станет None
• Базовый случай: пустой список (head = None)
• Три основных действия в цикле:
  1. Обработка текущего узла
  2. Перемещение к следующему узлу
  3. Проверка достижения конца списка

Область применения

• Вывод содержимого списка
• Поиск элементов
• Подсчет элементов
• Агрегация значений (сумма, среднее)
• Отладка и визуализация списков

Реализация

def traverse_list(head):
    """Итеративный обход связанного списка"""
    current = head        # Начинаем с головы списка
    result = []           # Список для хранения значений
    
    while current:        # Пока не достигли конца списка (None)
        result.append(current.val)  # Обрабатываем текущий узел
        current = current.next      # Перемещаемся к следующему узлу
    
    return result

def traverse_recursive(head):
    """Рекурсивный обход связанного списка"""
    result = []
    
    def traverse(node):
        """Вспомогательная рекурсивная функция"""
        if not node:      # Базовый случай: достигли конца списка
            return
        result.append(node.val)  # Обрабатываем текущий узел
        traverse(node.next)      # Рекурсивно обрабатываем следующий
    
    traverse(head)
    return result

---

Задача 2: Реверс связанного списка

Описание задачи

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

Принципы решения

• Три указателя:
  • prev: предыдущий узел (изначально None)
  • current: текущий узел
  • next_node: следующий узел (сохраняем перед изменением связей)
• Итеративный алгоритм:
  1. Сохранить ссылку на следующий узел
  2. Развернуть указатель текущего узла на предыдущий
  3. Сдвинуть указатели на одну позицию вперед
  4. Повторять пока не дойдем до конца
• Рекурсивный подход: реверс остатка списка, затем корректировка связей

Область применения

• Обработка данных в обратном порядке
• Палиндромы
• Реверс очереди или стека
• Алгоритмы "разверни и умножь"
• Системы отмены операций (undo)

Реализация

def reverse_list_iterative(head):
    """Итеративный разворот связанного списка"""
    prev = None          # Предыдущий узел, для первого узла это None
    current = head       # Текущий узел, начинаем с головы
    
    while current:       # Пока не дошли до конца списка
        next_node = current.next  # Сохраняем ссылку на следующий узел
        current.next = prev       # Разворачиваем указатель текущего узла
        prev = current            # Сдвигаем prev на текущий узел
        current = next_node       # Переходим к следующему узлу
    
    return prev          # Новая голова списка - последний обработанный узел

def reverse_list_recursive(head):
    """Рекурсивный разворот связанного списка"""
    # Базовый случай: пустой список или последний узел
    if not head or not head.next:
        return head
    
    # Рекурсивно разворачиваем остаток списка
    new_head = reverse_list_recursive(head.next)
    
    # Разворачиваем связь текущего узла
    head.next.next = head  # Следующий узел теперь указывает на текущий
    head.next = None       # Текущий узел становится последним
    
    return new_head

---

Задача 3: Обнаружение цикла в списке

Описание задачи

Определить, содержит ли связанный список цикл (когда последний узел ссылается на один из предыдущих узлов).

Принципы решения

• Алгоритм Флойда (Черепаха и Заяц):
  • Медленный указатель (tortoise) - движется на 1 узел за шаг
  • Быстрый указатель (hare) - движется на 2 узла за шаг
  • Если есть цикл, указатели встретятся
• Математическое обоснование: если есть цикл длины L, указатели встретятся через не более N шагов
• Дополнительные подходы:
  • Хэш-таблица посещенных узлов
  • Изменение структуры узлов (помечать посещенные)

Область применения

• Обнаружение зацикливания в системах
• Анализ графов и сетей
• Отладка рекурсивных структур
• Проверка корректности структур данных
• Обнаружение бесконечных циклов в автоматах

Реализация

def has_cycle(head):
    """Обнаружение цикла с помощью алгоритма Флойда"""
    if not head or not head.next:  # Список пуст или из одного элемента
        return False
    
    slow = head    # Черепаха - медленный указатель
    fast = head    # Заяц - быстрый указатель
    
    while fast and fast.next:  # Проверяем, что можно двигаться дальше
        slow = slow.next       # Черепаха на 1 шаг
        fast = fast.next.next  # Заяц на 2 шага
        
        if slow == fast:       # Указатели встретились - есть цикл
            return True
    
    return False  # fast достиг None - цикла нет

def has_cycle_hash(head):
    """Обнаружение цикла с использованием хэш-таблицы"""
    visited = set()  # Множество для хранения посещенных узлов
    current = head
    
    while current:
        if current in visited:  # Узел уже встречался - есть цикл
            return True
        visited.add(current)    # Помечаем узел как посещенный
        current = current.next
    
    return False

def find_cycle_start(head):
    """Нахождение начальной точки цикла (если есть)"""
    if not head or not head.next:
        return None
    
    # Первая фаза: обнаружение цикла
    slow = head
    fast = head
    has_cycle = False
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            has_cycle = True
            break
    
    if not has_cycle:
        return None
    
    # Вторая фаза: нахождение начала цикла
    # Перемещаем slow в head, двигаем оба указателя по одному шагу
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow  # Начало цикла

---

Задача 4: Слияние двух отсортированных списков

Описание задачи

Объединить два отсортированных связанных списка в один отсортированный список.

Принципы решения

• Использование фиктивной головы (dummy head): упрощает обработку граничных случаев
• Два указателя: по одному на каждый список
• Сравнение значений: выбираем меньший из двух текущих узлов
• Присоединение остатка: когда один список закончился, присоединяем остаток другого
• Итеративный подход:
  1. Создать фиктивный узел
  2. Сравнивать текущие узлы списков
  3. Присоединять меньший к результату
  4. Продолжать пока оба списка не закончатся

Область применения

• Слияние отсортированных данных
• Алгоритм сортировки слиянием для списков
• Объединение результатов нескольких запросов
• Балансировка загрузки
• Алгоритмы внешней сортировки

Реализация

def merge_two_lists(l1, l2):
    """Слияние двух отсортированных связанных списков"""
    # Создаем фиктивный узел для упрощения кода
    dummy = ListNode(0)
    current = dummy  # Указатель на текущий узел результата
    
    # Пока оба списка не пусты
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1     # Присоединяем узел из l1
            l1 = l1.next         # Перемещаемся в l1
        else:
            current.next = l2     # Присоединяем узел из l2
            l2 = l2.next         # Перемещаемся в l2
        
        current = current.next    # Перемещаем указатель результата
    
    # Присоединяем остаток непустого списка
    current.next = l1 if l1 else l2
    
    return dummy.next  # Возвращаем реальную голову (после dummy)

def merge_two_lists_recursive(l1, l2):
    """Рекурсивное слияние двух отсортированных списков"""
    # Базовые случаи
    if not l1:
        return l2
    if not l2:
        return l1
    
    # Выбираем меньший узел в качестве головы
    if l1.val < l2.val:
        l1.next = merge_two_lists_recursive(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_lists_recursive(l1, l2.next)
        return l2

def merge_k_lists(lists):
    """Слияние K отсортированных списков (усложненная задача)"""
    if not lists:
        return None
    
    # Используем подход "разделяй и властвуй"
    def merge_lists(left, right):
        """Вспомогательная функция для слияния диапазона списков"""
        if left == right:  # Один список в диапазоне
            return lists[left]
        
        mid = (left + right) // 2
        l1 = merge_lists(left, mid)     # Левая половина
        l2 = merge_lists(mid + 1, right)  # Правая половина
        return merge_two_lists(l1, l2)   # Слияние двух списков
    
    return merge_lists(0, len(lists) - 1)

---

Задача 5: Удаление N-го узла с конца

Описание задачи

Удалить N-й узел с конца связанного списка за один проход.

Принципы решения

• Два указателя с отставанием:
  • fast: быстрый указатель, уходит вперед на N+1 шаг
  • slow: медленный указатель, начинает с головы
  • Когда fast достигнет конца, slow будет перед удаляемым узлом
• Алгоритм:
  1. fast продвигается на N шагов вперед
  2. Если fast стал None, значит удаляем голову
  3. Иначе двигаем оба указателя пока fast не достигнет конца
  4. slow.next = slow.next.next
• Особые случаи:
  • Удаление головы списка
  • Удаление последнего узла
  • N больше длины списка

Область применения

• Удаление элементов по позиции с конца
• Реализация LRU (Least Recently Used) кэша
• Обработка стека вызовов
• Системы с приоритетами
• Управление памятью

Реализация

def remove_nth_from_end(head, n):
    """Удаление N-го узла с конца списка за один проход"""
    # Создаем фиктивный узел для обработки удаления головы
    dummy = ListNode(0)
    dummy.next = head
    
    fast = dummy
    slow = dummy
    
    # Перемещаем fast на n+1 позиций вперед
    for _ in range(n + 1):
        if not fast:  # Если n больше длины списка
            return head
        fast = fast.next
    
    # Двигаем оба указателя пока fast не достигнет конца
    while fast:
        fast = fast.next
        slow = slow.next
    
    # slow теперь указывает на узел перед удаляемым
    slow.next = slow.next.next
    
    return dummy.next  # Возвращаем реальную голову

def remove_nth_from_end_two_pass(head, n):
    """Удаление N-го узла с конца (два прохода)"""
    # Первый проход: вычисляем длину списка
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    
    # Вычисляем позицию с начала (0-based)
    position_from_start = length - n
    
    # Если удаляем голову
    if position_from_start == 0:
        return head.next
    
    # Второй проход: находим и удаляем узел
    current = head
    for _ in range(position_from_start - 1):
        current = current.next
    
    current.next = current.next.next
    return head

---

Задача 6: Поиск середины списка

Описание задачи

Найти средний узел связанного списка. Если список имеет четную длину, вернуть второй из двух средних узлов.

Принципы решения

• Алгоритм быстрого и медленного указателя:
  • slow: двигается на 1 узел за шаг
  • fast: двигается на 2 узла за шаг
  • Когда fast достигнет конца, slow будет в середине
• Особенности для четной длины: вернуть второй средний узел
• Альтернативный подход:
  1. Посчитать длину списка
  2. Пройти до середины

Область применения

• Разделение списка пополам (сортировка слиянием)
• Балансировка структур данных
• Поиск медианы в потоке данных
• Разбиение на две части для параллельной обработки
• Определение центра в сетях

Реализация

def middle_node(head):
    """Нахождение середины списка с помощью двух указателей"""
    if not head or not head.next:
        return head
    
    slow = head
    fast = head
    
    # fast движется в два раза быстрее slow
    while fast and fast.next:
        slow = slow.next          # 1 шаг
        fast = fast.next.next     # 2 шага
    
    return slow  # slow в середине, когда fast достиг конца

def middle_node_with_first_middle(head):
    """Нахождение первого среднего узла для четной длины"""
    if not head or not head.next:
        return head
    
    slow = head
    fast = head
    prev = None  # Для сохранения предыдущего узла slow
    
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    
    # Для четной длины возвращаем первый средний узел
    if fast is None:  # Четная длина
        return prev
    
    return slow  # Нечетная длина

def find_middle_and_split(head):
    """Нахождение середины и разделение списка на две части"""
    if not head or not head.next:
        return head, None
    
    slow = head
    fast = head
    prev = None
    
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    
    # Разделяем список на две части
    if prev:
        prev.next = None  # Обрываем первую половину
        return head, slow  # Возвращаем обе половины
    else:
        # Список из одного или двух элементов
        second_half = head.next
        head.next = None
        return head, second_half

---

Задача 7: Проверка палиндрома в связанном списке

Описание задачи

Проверить, является ли последовательность значений в связанном списке палиндромом (читается одинаково с начала и с конца).

Принципы решения

• Подход с реверсом второй половины:
  1. Найти середину списка
  2. Развернуть вторую половину
  3. Сравнить первую и развернутую вторую половины
  4. Восстановить исходный список (опционально)
• С использованием стека:
  • Заполнить стек первой половиной значений
  • Сравнить со второй половиной
• Рекурсивный подход: сравнение начала и конца с помощью рекурсии

Область применения

• Проверка симметричности последовательностей
• Анализ строк и последовательностей
• Задачи на палиндромы
• Проверка корректности данных
• Алгоритмы сжатия

Реализация

def is_palindrome(head):
    """Проверка, является ли список палиндромом (с реверсом половины)"""
    if not head or not head.next:
        return True
    
    # Шаг 1: Находим середину списка
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Шаг 2: Разворачиваем вторую половину
    second_half = reverse_list_iterative(slow)
    
    # Шаг 3: Сравниваем первую и вторую половины
    first_half = head
    second_half_copy = second_half
    is_pal = True
    
    while second_half:
        if first_half.val != second_half.val:
            is_pal = False
            break
        first_half = first_half.next
        second_half = second_half.next
    
    # Шаг 4: Восстанавливаем исходный список
    reverse_list_iterative(second_half_copy)
    
    return is_pal

def is_palindrome_stack(head):
    """Проверка палиндрома с использованием стека"""
    if not head or not head.next:
        return True
    
    # Находим середину и заполняем стек
    slow = head
    fast = head
    stack = []
    
    while fast and fast.next:
        stack.append(slow.val)
        slow = slow.next
        fast = fast.next.next
    
    # Если нечетное количество элементов, пропускаем средний
    if fast:  # fast не None значит нечетное количество
        slow = slow.next
    
    # Сравниваем оставшуюся часть со стеком
    while slow:
        if slow.val != stack.pop():
            return False
        slow = slow.next
    
    return True

def is_palindrome_recursive(head):
    """Проверка палиндрома с помощью рекурсии"""
    front_pointer = head
    
    def recursively_check(current_node):
        nonlocal front_pointer
        if not current_node:
            return True
        
        # Рекурсивно проверяем остаток списка
        if not recursively_check(current_node.next):
            return False
        
        # Сравниваем текущий узел с соответствующим узлом с начала
        if current_node.val != front_pointer.val:
            return False
        
        front_pointer = front_pointer.next
        return True
    
    return recursively_check(head)

---

Задача 8: Пересечение двух связанных списков

Описание задачи

Найти узел, в котором два связанных списка пересекаются. Если пересечения нет, вернуть None.

Принципы решения

• Подход с двумя указателями:
  • Указатель A проходит список A затем переходит в список B
  • Указатель B проходит список B затем переходит в список A
  • Если списки пересекаются, указатели встретятся в точке пересечения
  • Если не пересекаются, оба станут None одновременно
• Математическое обоснование: оба указателя пройдут одинаковое расстояние
• Альтернативные подходы:
  • Хэш-таблица узлов первого списка
  • Выравнивание по длине

Область применения

• Обнаружение общих элементов
• Анализ графов зависимостей
• Системы контроля версий (merge point)
• Обнаружение циклических зависимостей
• Анализ сетевых пакетов

Реализация

def get_intersection_node(headA, headB):
    """Нахождение точки пересечения двух связанных списков"""
    if not headA or not headB:
        return None
    
    pointerA = headA
    pointerB = headB
    
    # Оба указателя проходят оба списка
    # Если списки пересекаются, встретятся в точке пересечения
    # Если нет, оба станут None одновременно
    
    while pointerA != pointerB:
        # Переходим к следующему узлу или в другой список
        pointerA = pointerA.next if pointerA else headB
        pointerB = pointerB.next if pointerB else headA
    
    return pointerA  # Может быть None или узел пересечения

def get_intersection_node_length(headA, headB):
    """Нахождение пересечения с предварительным вычислением длин"""
    # Вычисляем длины обоих списков
    def get_length(head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length
    
    lenA = get_length(headA)
    lenB = get_length(headB)
    
    # Выравниваем начала списков
    currA, currB = headA, headB
    
    if lenA > lenB:
        for _ in range(lenA - lenB):
            currA = currA.next
    else:
        for _ in range(lenB - lenA):
            currB = currB.next
    
    # Ищем пересечение
    while currA and currB:
        if currA == currB:
            return currA
        currA = currA.next
        currB = currB.next
    
    return None

def get_intersection_node_hash(headA, headB):
    """Нахождение пересечения с использованием хэш-таблицы"""
    visited = set()
    current = headA
    
    # Сохраняем все узлы первого списка
    while current:
        visited.add(current)
        current = current.next
    
    # Проверяем узлы второго списка
    current = headB
    while current:
        if current in visited:
            return current
        current = current.next
    
    return None

---

Задача 9: Удаление дубликатов из отсортированного списка

Описание задачи

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

Принципы решения

• Итеративный подход с одним указателем:
  • current: указатель на текущий узел
  • Сравнивать current.val с current.next.val
  • Если равны, пропустить следующий узел
• Алгоритм:
  1. Начинаем с головы
  2. Пока current и current.next не None
  3. Если значения совпадают, current.next = current.next.next
  4. Иначе двигаем current вперед
• Для несортированного списка: использовать хэш-таблицу для отслеживания уникальных значений

Область применения

• Очистка данных от дубликатов
• Сжатие данных
• Оптимизация хранения
• Предварительная обработка данных
• Анализ логов и транзакций

Реализация

def delete_duplicates_sorted(head):
    """Удаление дубликатов из отсортированного списка"""
    if not head or not head.next:
        return head
    
    current = head
    
    while current and current.next:
        if current.val == current.next.val:
            # Пропускаем следующий узел (удаляем дубликат)
            current.next = current.next.next
        else:
            # Переходим к следующему узлу
            current = current.next
    
    return head

def delete_duplicates_sorted_ii(head):
    """Удаление всех узлов, имеющих дубликаты (оставляем только уникальные)"""
    # Создаем фиктивный узел для обработки удаления головы
    dummy = ListNode(0)
    dummy.next = head
    
    prev = dummy  # Указатель на предыдущий уникальный узел
    current = head
    
    while current:
        # Пропускаем все дубликаты текущего узла
        is_duplicate = False
        while current.next and current.val == current.next.val:
            current = current.next
            is_duplicate = True
        
        if is_duplicate:
            # Удаляем все узлы с этим значением
            prev.next = current.next
        else:
            # Текущий узел уникален
            prev = prev.next
        
        current = current.next
    
    return dummy.next

def delete_duplicates_unsorted(head):
    """Удаление дубликатов из несортированного списка"""
    if not head or not head.next:
        return head
    
    visited = set()  # Множество для хранения уникальных значений
    current = head
    visited.add(current.val)  # Добавляем значение головы
    
    while current and current.next:
        if current.next.val in visited:
            # Удаляем следующий узел
            current.next = current.next.next
        else:
            # Добавляем значение в множество и двигаемся дальше
            visited.add(current.next.val)
            current = current.next
    
    return head

---

Задача 10: Сортировка связанного списка

Описание задачи

Отсортировать связанный список по возрастанию значений.

Принципы решения

• Сортировка слиянием (наиболее эффективная для списков):
  1. Разделить список на две половины
  2. Рекурсивно отсортировать каждую половину
  3. Слить отсортированные половины
• Преимущества сортировки слиянием:
  • Гарантированная O(n log n) сложность
  • Стабильность
  • Хорошо работает со связанными списками
• Альтернативы:
  • Пузырьковая сортировка (O(n²), только для обучения)
  • Преобразование в массив, сортировка, восстановление списка

Область применения

• Сортировка больших объемов данных
• Подготовка данных для бинарного поиска
• Алгоритмы внешней сортировки
• Обработка потоков данных
• Оптимизация запросов к базам данных

Реализация

def sort_list(head):
    """Сортировка связанного списка слиянием"""
    # Базовые случаи
    if not head or not head.next:
        return head
    
    # Шаг 1: Разделить список на две половины
    def split_list(head):
        """Разделение списка на две половины"""
        if not head or not head.next:
            return head, None
        
        slow = head
        fast = head
        prev = None
        
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        
        # Разрываем связь между половинами
        if prev:
            prev.next = None
        
        return head, slow
    
    # Шаг 2: Слияние двух отсортированных списков
    def merge_sorted(l1, l2):
        """Слияние двух отсортированных списков"""
        dummy = ListNode(0)
        current = dummy
        
        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
        
        current.next = l1 if l1 else l2
        return dummy.next
    
    # Рекурсивная сортировка
    left, right = split_list(head)
    left_sorted = sort_list(left)
    right_sorted = sort_list(right)
    
    return merge_sorted(left_sorted, right_sorted)

def bubble_sort_list(head):
    """Пузырьковая сортировка списка (учебный пример)"""
    if not head or not head.next:
        return head
    
    swapped = True
    while swapped:
        swapped = False
        current = head
        prev = None
        
        while current and current.next:
            if current.val > current.next.val:
                # Меняем узлы местами
                next_node = current.next
                current.next = next_node.next
                next_node.next = current
                
                if prev:
                    prev.next = next_node
                else:
                    head = next_node
                
                prev = next_node
                swapped = True
            else:
                prev = current
                current = current.next
    
    return head

---

Дополнительные полезные функции

Вспомогательные функции для работы со списками

def create_linked_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 print_linked_list(head):
    """Вывод связанного списка"""
    current = head
    result = []
    while current:
        result.append(str(current.val))
        current = current.next
    print(" -> ".join(result) + " -> None")

def get_length(head):
    """Получение длины связанного списка"""
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    return length

def copy_linked_list(head):
    """Копирование связанного списка"""
    if not head:
        return None
    
    new_head = ListNode(head.val)
    current_old = head.next
    current_new = new_head
    
    while current_old:
        current_new.next = ListNode(current_old.val)
        current_old = current_old.next
        current_new = current_new.next
    
    return new_head

Советы для решения задач на связанные списки

1. Всегда проверяйте крайние случаи:

   • Пустой список (head = None)
   • Список из одного элемента
   • Список из двух элементов
   • Очень длинный список

2. Используйте фиктивный узел (dummy node):

   • Упрощает обработку удаления/вставки в начале
   • Избавляет от необходимости специальной обработки головы

3. Будьте осторожны с указателями:

   • Сохраняйте следующий узел перед изменением связей
   • Проверяйте существование узла перед доступом к его полям

4. Визуализируйте задачу:

   • Рисуйте диаграммы связей
   • Отмечайте текущие положения указателей
   • Продумывайте изменения шаг за шагом

5. Оптимизация для конкретных задач:

   • Для обнаружения циклов - алгоритм Флойда
   • Для поиска середины - два указателя
   • Для палиндромов - реверс половины списка
   • Для сортировки - сортировка слиянием

Сложность операций

Операция	Время	Память
Обход	O(n)	O(1)
Поиск элемента	O(n)	O(1)
Вставка в начало	O(1)	O(1)
Вставка в конец	O(n)	O(1)
Вставка по индексу	O(n)	O(1)
Удаление из начала	O(1)	O(1)
Удаление из конца	O(n)	O(1)
Реверс	O(n)	O(1)
Сортировка слиянием	O(n log n)	O(log n) рекурсия
Обнаружение цикла	O(n)	O(1)

Это полное пособие покрывает основные задачи на связанные списки в Python с детальными объяснениями принципов решения и областей применения каждого алгоритма.