Нахождение середины связного списка

Решение: Середина связного списка за один проход

Понимание задачи

Найти средний элемент в О(1) дополнительной памяти за один проход. Используем технику двух указателей с разной скоростью.

Определение узла

class ListNode:
    def __init__(self, val: int):
        self.val = val
        self.next = None

Решение 1: Техника черепахи и зайца (Two-Pointer)

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

Как работает:

• slow движется на 1 элемент за раз
• fast движется на 2 элемента за раз
• Когда fast достигает конца, slow находится в середине

Time Complexity: O(n) Space Complexity: O(1)

Решение 2: С обработкой четных/нечетных списков

def find_middle_with_info(head: ListNode) -> tuple[ListNode, int]:
    slow = head
    fast = head
    count = 0
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        count += 1
    
    # Если fast не None, список нечетной длины
    is_odd = fast is not None
    
    return slow, is_odd

Решение 3: Функция для создания тестового списка

def create_linked_list(values: list[int]) -> ListNode:
    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(head: ListNode) -> str:
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    return " -> ".join(result)

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

# Пример 1: Нечетная длина
head1 = create_linked_list([1, 2, 3, 4, 5])
print(f"Список: {list_to_string(head1)}")
middle1 = find_middle_single_pass(head1)
print(f"Середина: {middle1.val}")  # 3

# Пример 2: Четная длина
head2 = create_linked_list([1, 2, 3, 4])
print(f"Список: {list_to_string(head2)}")
middle2 = find_middle_single_pass(head2)
print(f"Середина (после середины): {middle2.val}")  # 3

# Пример 3: Один элемент
head3 = create_linked_list([1])
middle3 = find_middle_single_pass(head3)
print(f"Середина: {middle3.val}")  # 1

# Пример 4: Два элемента
head4 = create_linked_list([1, 2])
middle4 = find_middle_single_pass(head4)
print(f"Середина: {middle4.val}")  # 2

Визуализация алгоритма

Для списка [1, 2, 3, 4, 5]:

Начало: slow: 1, fast: 1

Итерация 1: slow: 2, fast: 3

Итерация 2: slow: 3, fast: 5

Итерация 3: slow: 3, fast: None (конец)

slow указывает на 3 - это середина!

Решение 4: Возврат обоих концов списка при четной длине

def find_middle_return_both(head: ListNode) -> ListNode:
    slow = head
    fast = head
    prev = None
    
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    
    # Для четной длины возвращаем первый элемент второй половины
    # Для нечетной длины возвращаем точную середину
    
    return slow

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

def test_find_middle():
    # Один элемент
    head = create_linked_list([5])
    assert find_middle_single_pass(head).val == 5
    
    # Два элемента
    head = create_linked_list([1, 2])
    assert find_middle_single_pass(head).val == 2
    
    # Три элемента
    head = create_linked_list([1, 2, 3])
    assert find_middle_single_pass(head).val == 2
    
    # Четыре элемента
    head = create_linked_list([1, 2, 3, 4])
    assert find_middle_single_pass(head).val == 3
    
    # Пять элементов
    head = create_linked_list([1, 2, 3, 4, 5])
    assert find_middle_single_pass(head).val == 3
    
    # Даже большой список
    head = create_linked_list(list(range(1, 101)))
    middle = find_middle_single_pass(head)
    assert middle.val == 51  # Вторая половина для четной длины
    
    print("Все тесты пройдены!")

test_find_middle()

Альтернатива: Два прохода (для сравнения)

def find_middle_two_passes(head: ListNode) -> ListNode:
    # Первый проход: подсчитаем длину
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    
    # Второй проход: найдём середину
    mid_position = length // 2
    current = head
    for _ in range(mid_position):
        current = current.next
    
    return current

Сравнение подходов

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

Основной алгоритм (Решение 1):

• Простой и эффективный
• O(1) дополнительная память
• Один проход по списку
• Часто встречается на собеседованиях

Ключевые моменты:

• fast = fast.next.next (быстрый указатель)
• slow = slow.next (медленный указатель)
• Цикл пока fast и fast.next не None
• Гарантированно находит середину за один проход