Поиск середины связанного списка (с анимированными примерами)
19 декабря 2022 г.Учитывая заголовок односвязного списка, вернуть средний узел связанного списка.
Если есть два средних узла, вернуть второй средний узел.
Пример 1:
Ввод: head = [1,2,3,4,5] Вывод: [3,4,5] Объяснение: Средний узел списка — это узел 3.
Пример 2:
Ввод: head = [1,2,3,4,5,6] Вывод: [4,5,6] Объяснение: Поскольку в списке есть два средних узла со значениями 3 и 4, мы возвращаем второй.
Ограничения:
Количество узлов в списке находится в диапазоне [1, 100]. 1 <= Node.val <= 100
Решение
Подход 1: два прохода
- Найдите длину связанного списка, пройдясь по списку.
- Найдите средний узел, снова перейдя по списку к середине.
- Вернуть средний узел
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def middle_node(head: ListNode) -> ListNode:
length = 0
current = head
while current:
length += 1
current = current.next
middle = length // 2
current = head
for _ in range(middle):
current = current.next
return current
Временная сложность: O(n) Пространственная сложность: O(1)
https://youtu.be/xcsDK3mziCM?embedable=true
Подход 2: один проход
- Используйте два указателя, один быстрый, а другой медленный.
- Перемещайте быстрый указатель на два узла за раз, а медленный указатель на один узел.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def middle_node(head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Временная сложность: O(n) Пространственная сложность: O(1)
https://youtu.be/vD0XdyM_Wwk?embedable=true
Оригинал