Учебная платформа AST-STUDY

← Назад к курсу

20 типовых задач по связанным спискам на Python с решениями

1. Обратить связанный список

def reverseList(head: ListNode) -> ListNode:
    prev = None
    current = head
    
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    
    return prev

2. Найти средний элемент

def middleNode(head: ListNode) -> ListNode:
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow

3. Определить есть ли цикл в списке (Floyd's Cycle Detection)

def hasCycle(head: ListNode) -> bool:
    if not head:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

4. Найти начало цикла (если есть)

def detectCycle(head: ListNode) -> ListNode:
    if not head or not head.next:
        return None
    
    slow = fast = head
    
    # 1. Обнаружить цикл
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            break
    else:
        return None  # Цикла нет
    
    # 2. Найти начало цикла
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

5. Удалить N-й элемент с конца

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0, head)
    first = second = dummy
    
    # Первый указатель на n+1 позицию вперед
    for _ in range(n + 1):
        first = first.next
    
    # Двигаем оба указателя
    while first:
        first = first.next
        second = second.next
    
    # Удаляем узел
    second.next = second.next.next
    
    return dummy.next

6. Удалить дубликаты из отсортированного списка

def deleteDuplicates(head: ListNode) -> ListNode:
    current = head
    
    while current and current.next:
        if current.val == current.next.val:
            current.next = current.next.next
        else:
            current = current.next
    
    return head

7. Проверить является ли список палиндромом

def isPalindrome(head: ListNode) -> bool:
    # 1. Найти середину
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # 2. Развернуть вторую половину
    prev = None
    while slow:
        next_node = slow.next
        slow.next = prev
        prev = slow
        slow = next_node
    
    # 3. Сравнить две половины
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    
    return True

8. Объединить K отсортированных списков

import heapq

def mergeKLists(lists: List[ListNode]) -> ListNode:
    heap = []
    
    # Добавляем первые элементы каждого списка в кучу
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))
    
    dummy = ListNode()
    current = dummy
    
    while heap:
        val, i, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    
    return dummy.next

9. Поменять узлы попарно

def swapPairs(head: ListNode) -> ListNode:
    dummy = ListNode(0, head)
    prev = dummy
    
    while prev.next and prev.next.next:
        first = prev.next
        second = first.next
        
        # Меняем местами
        first.next = second.next
        second.next = first
        prev.next = second
        
        # Перемещаем prev
        prev = first
    
    return dummy.next

10. Развернуть список в группах по K элементов

def reverseKGroup(head: ListNode, k: int) -> ListNode:
    def reverse(head, tail):
        prev = tail.next
        curr = head
        
        while prev != tail:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        
        return tail, head
    
    dummy = ListNode(0, head)
    prev = dummy
    
    while head:
        tail = prev
        
        # Проверяем достаточно ли элементов
        for i in range(k):
            tail = tail.next
            if not tail:
                return dummy.next
        
        next_group = tail.next
        
        # Разворачиваем группу
        head, tail = reverse(head, tail)
        
        # Восстанавливаем связи
        prev.next = head
        tail.next = next_group
        
        # Переходим к следующей группе
        prev = tail
        head = tail.next
    
    return dummy.next

11. Разделить список на две части

def splitList(head: ListNode) -> tuple:
    if not head:
        return None, None
    
    slow = head
    fast = head.next
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    second = slow.next
    slow.next = None
    
    return head, second

12. Отсортировать список (Merge Sort)

def sortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    
    # 1. Разделить список
    def split(head):
        slow = head
        fast = head.next
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        mid = slow.next
        slow.next = None
        return head, mid
    
    # 2. Объединить два отсортированных списка
    def merge(l1, l2):
        dummy = ListNode()
        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
    
    # 3. Рекурсивная сортировка
    left, right = split(head)
    left_sorted = sortList(left)
    right_sorted = sortList(right)
    
    return merge(left_sorted, right_sorted)

13. Удалить все элементы с заданным значением

def removeElements(head: ListNode, val: int) -> ListNode:
    dummy = ListNode(0, head)
    current = dummy
    
    while current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
    
    return dummy.next

14. Найти пересечение двух списков

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB:
        return None
    
    p1, p2 = headA, headB
    
    while p1 != p2:
        p1 = p1.next if p1 else headB
        p2 = p2.next if p2 else headA
    
    return p1

15. Вставить элемент в отсортированный список

def insertIntoSortedList(head: ListNode, val: int) -> ListNode:
    dummy = ListNode(float('-inf'), head)
    current = dummy
    
    while current.next and current.next.val < val:
        current = current.next
    
    new_node = ListNode(val, current.next)
    current.next = new_node
    
    return dummy.next

16. Развернуть список между позициями m и n

def reverseBetween(head: ListNode, m: int, n: int) -> ListNode:
    if m == n:
        return head
    
    dummy = ListNode(0, head)
    prev = dummy
    
    # Находим узел перед началом разворота
    for _ in range(m - 1):
        prev = prev.next
    
    # Разворачиваем часть списка
    current = prev.next
    reverse_head = None
    
    for _ in range(n - m + 1):
        next_node = current.next
        current.next = reverse_head
        reverse_head = current
        current = next_node
    
    # Соединяем части
    prev.next.next = current
    prev.next = reverse_head
    
    return dummy.next

17. Скопировать список со случайными указателями

class Node:
    def __init__(self, val=0, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyRandomList(head: Node) -> Node:
    if not head:
        return None
    
    # 1. Создать копии рядом с оригинальными
    current = head
    while current:
        new_node = Node(current.val, current.next, None)
        current.next = new_node
        current = new_node.next
    
    # 2. Скопировать random указатели
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next
    
    # 3. Разделить списки
    old_current = head
    new_head = head.next
    new_current = new_head
    
    while old_current:
        old_current.next = old_current.next.next
        if new_current.next:
            new_current.next = new_current.next.next
        
        old_current = old_current.next
        new_current = new_current.next
    
    return new_head

18. Сложение двух чисел представленных списками

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    current = dummy
    carry = 0
    
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        
        total = val1 + val2 + carry
        carry = total // 10
        
        current.next = ListNode(total % 10)
        current = current.next
        
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
    
    return dummy.next

19. Удалить узел (имея только доступ к нему)

def deleteNode(node: ListNode):
    """
    Удаляет узел, имея только доступ к нему.
    Нельзя удалить последний узел этим методом.
    """
    node.val = node.next.val
    node.next = node.next.next

20. Разделить список по значению X

def partition(head: ListNode, x: int) -> ListNode:
    before = before_head = ListNode(0)
    after = after_head = ListNode(0)
    
    while head:
        if head.val < x:
            before.next = head
            before = before.next
        else:
            after.next = head
            after = after.next
        
        head = head.next
    
    after.next = None
    before.next = after_head.next
    
    return before_head.next

Полезные вспомогательные функции:

def printList(head: ListNode):
    """Печать списка"""
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "Empty list")

def createList(values: list) -> ListNode:
    """Создание списка из массива"""
    dummy = ListNode()
    current = dummy
    for val in values:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

def listToArray(head: ListNode) -> list:
    """Преобразование списка в массив"""
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

Основные паттерны решения:

  1. Два указателя (быстрый и медленный) - для поиска середины, цикла
  2. Фиктивный узел - для упрощения обработки граничных случаев
  3. Рекурсия - для задач разворота, сортировки
  4. Итеративное разворачивание - для обратных операций
  5. Слияние - для работы с отсортированными списками

Эти задачи покрывают большинство типовых вопросов по связанным спискам на собеседованиях!

Дополнительный материал

Вопросы учеников к ИИ-помощнику и ответы по теме урока

Вопрос: Анонимный пользователь · 2025-12-19 10:31
# 2. Найти начало цикла slow = head while slow != fast: slow = slow.next fast = fast.next return slow Поясни, почему будет начало цикла
Ответ ИИ:

Отлично, разберем этот ключевой момент алгоритма Флойда.

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

Пошаговое объяснение:

  1. Обозначим расстояния:

    • D — расстояние от головы списка (head) до начала цикла.
    • C — длина цикла.
    • K — расстояние от начала цикла до точки встречи slow и fast внутри цикла (после первого этапа алгоритма).

  2. Что произошло на первом этапе (обнаружение цикла):

    • slow прошел расстояние: D + K.
    • fast прошел расстояние: D + K + n * C, где n — целое число полных кругов по циклу, которые fast успел сделать до встречи.
    • Так как fast двигался в 2 раза быстрее, получаем уравнение:
      2 * (D + K) = D + K + n * C
      Упрощаем: D + K = n * C
      Или: D = n * C - K.

  3. Что означает второе уравнение D = n * C - K:

    • Расстояние от головы до начала цикла (D) равно целому числу полных циклов (n*C) минус расстояние от точки встречи до начала цикла (K).
    • Если теперь slow поставить в начало (head), а fast оставить в точке встречи и начать двигать их с одинаковой скоростью (по 1 шагу), то:
      • slow за D шагов придет в начало цикла.
      • fast за D шагов переместится из точки встречи. Из уравнения видно, что D = n*C - K. Значит, fast пройдет n полных кругов и отступит на K шагов назад от точки встречи, что и приведет его ровно в начало цикла. Они встретятся там.

Короткое упражнение для закрепления:
Возьми лист бумаги и нарисуй список: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (цикл: 3->4->5->3).
Пройди алгоритм по шагам, вычисли D, C, K и убедись, что на втором этапе указатели действительно встретятся на узле 3.