Слияние, разделение и поиск с конца
Объединяйте два отсортированных связных списка за O(n), разделяйте список в середине с помощью медленного и быстрого указателей и находите n-й узел с конца
«Слияние, разделение и поиск с конца» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Три основных шаблона для связных списков
В этом уроке рассматриваются три базовые операции со связными списками, которые постоянно используются как строительные блоки в более сложных задачах: слияние двух отсортированных списков (используется в сортировке слиянием и слиянии k списков), разделение списка по середине (используется в сортировке слиянием и обнаружении палиндрома) и поиск n-го узла с конца (используется при удалении n-го узла с конца).
Все три операции основаны на уже знакомых вам приемах: фиктивном головном узле, медленном и быстром указателях и тщательном отслеживании границ.
Слияние двух отсортированных списков
LeetCode 21 «Merge Two Sorted Lists»: даны два отсортированных связных списка, требуется вернуть один объединенный отсортированный список. Используйте фиктивную голову и указатель curr на хвост. На каждом шаге сравнивайте головы двух списков и присоединяйте меньший узел к curr. Когда один список закончится, присоедините оставшуюся часть другого. Время: O(n+m), память: O(1) (перестройка связей на месте).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2 # attach remaining nodes
return dummy.next
def build(arr):
d = ListNode(); c = d
for v in arr:
c.next = ListNode(v); c = c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))Пошаговая трассировка слияния
Проследим работу mergeTwoLists([1,2,4], [1,3,4]): сравниваем 1 и 1 — выбираем l1(1), перемещаем l1 к 2. Сравниваем 2 и 1 — выбираем l2(1), перемещаем l2 к 3. Сравниваем 2 и 3 — выбираем l1(2), перемещаем l1 к 4. Сравниваем 4 и 3 — выбираем l2(3), перемещаем l2 к 4. Сравниваем 4 и 4 — выбираем l1(4), перемещаем l1 к None. Присоединяем оставшийся l2(4). Результат: [1,1,2,3,4,4].
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
step = 0
while l1 and l2:
step += 1
if l1.val <= l2.val:
print(f'Step {step}: pick l1({l1.val})')
curr.next = l1; l1 = l1.next
else:
print(f'Step {step}: pick l2({l2.val})')
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
mergeTwoLists(build([1,2,4]),build([1,3,4]))Поиск середины с помощью медленного и быстрого указателей
Чтобы разделить список по середине, используйте шаблон с медленным и быстрым указателями. slow продвигается на 1 шаг, а fast — на 2 шага. Когда fast достигает None (или последнего узла), slow находится в середине. Для списка четной длины это первый из двух средних узлов, что является стандартным вариантом разделения для сортировки слиянием.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_at_mid(head):
'''Returns (first_half_head, second_half_head).'''
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # second half starts here
slow.next = None # sever the list
return head, mid
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second)) # [1,2,3] [4,5]Сортировка слиянием связного списка
LeetCode 148 «Сортировка списка»: отсортируйте связный список за O(n log n) времени и с использованием O(log n) памяти. Подход заключается в следующем: разделите список посередине, рекурсивно отсортируйте обе половины и объедините их. Сортировка слиянием связного списка естественна, поскольку разделение по середине занимает O(n) времени (в отличие от O(1) для массивов), но общая сложность всё равно составляет O(n log n), а стек вызовов использует только O(log n) памяти.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(head):
if not head or not head.next:
return head
# Split
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# Recurse
left = sortList(head)
right = sortList(mid)
# Merge
dummy = ListNode(0)
curr = dummy
while left and right:
if left.val <= right.val:
curr.next = left; left = left.next
else:
curr.next = right; right = right.next
curr = curr.next
curr.next = left or right
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(sortList(build([4,2,1,3])))) # [1,2,3,4]Поиск n-го узла с конца
LeetCode 19 «Удаление n-го узла с конца списка»: найдите n-й узел от хвоста за один проход. Используйте два указателя, расстояние между которыми составляет ровно n узлов. Продвиньте fast на n шагов вперёд относительно slow. Затем перемещайте оба указателя одновременно, пока fast не достигнет последнего узла. В этот момент slow указывает на (n+1)-й узел с конца — предшественник узла, который нужно удалить.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = dummy
for _ in range(n + 1): # advance fast n+1 steps
fast = fast.next
slow = dummy
while fast: # advance both until fast is None
slow = slow.next
fast = fast.next
slow.next = slow.next.next # remove nth node
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(removeNthFromEnd(build([1,2,3,4,5]), 2))) # [1,2,3,5]Зачем нужны n+1 шагов при удалении n-го узла
Главная тонкость заключается в том, что быстрый указатель нужно продвинуть на n+1 шагов (а не на n) от фиктивной головы списка. После n+1 шагов быстрый указатель опережает медленный на n+1 позиций (оба начинают с фиктивной головы). Когда быстрый указатель достигает пустого значения (позиции сразу за хвостом), медленный находится на n+1 позиций раньше пустого значения — то есть на позиции (length - n - 1), если считать с нуля, или у предшественника целевого узла. Благодаря этому выражение slow.next = slow.next.next корректно удаляет n-й узел с конца.
# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow) 1 2 3(fast) 4 5 None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')Пересечение двух связных списков
LeetCode 160 «Пересечение двух связных списков»: найдите узел, в котором два списка впервые пересекаются. Приём с использованием O(1) дополнительной памяти: перемещайте два указателя, по одному для каждого списка. Когда указатель достигает конца списка, перенаправьте его к началу другого списка. Не более чем за сумму длин A и B шагов оба указателя пройдут одинаковое общее расстояние и должны оказаться в узле пересечения (или оба у пустого значения, если пересечения нет).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a # None if no intersection
# Build: A: 4->1->\ B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val) # 8Объединение K отсортированных списков (разделяй и властвуй)
LeetCode 23 «Объединение K отсортированных списков»: по данным k отсортированным спискам объедините их в один. Оптимальный подход — последовательно объединять пары списков методом «разделяй и властвуй», уменьшая количество списков вдвое на каждом раунде. Для k списков средней длины n это занимает O(n k log k) времени по сравнению с O(n k²) при последовательном объединении. Подход с минимальной кучей также имеет сложность O(n k log k).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
def merge_two(l1, l2):
dummy = ListNode(0); curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1; l1 = l1.next
else:
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
if not lists: return None
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i+1 < len(lists) else None
merged.append(merge_two(l1, l2))
lists = merged
return lists[0]
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists))) # [1,1,2,3,4,4,5,6]Связный список с нечётными и чётными позициями
LeetCode 328 «Связный список с нечётными и чётными позициями»: сначала сгруппируйте все узлы с нечётными индексами, затем узлы с чётными индексами (нумерация начинается с 1). Подход заключается в поддержании двух отдельных цепочек (нечётной и чётной) и их соединении после завершения обхода. Достаточно одного прохода по списку, поэтому алгоритм работает за O(n) времени и использует O(1) памяти. Это наглядный пример одновременного перемещения двух указателей с разным шагом.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(oddEvenList(build([1,2,3,4,5])))) # [1,3,5,2,4]Собираем всё вместе
Три шаблона этого урока — объединение отсортированных списков, разделение по середине и поиск n-го узла с конца — объединяет одна идея: используйте дополнительные переменные-указатели, чтобы отслеживать позиции без дополнительной памяти. Фиктивная голова упрощает объединение и удаление; разрыв между медленным и быстрым указателями фиксирует определённую относительную позицию; предварительное перемещение одного указателя создаёт нужное расстояние.
На собеседовании назовите используемый шаблон до написания кода: «Я использую технику двух указателей с заданным расстоянием, чтобы найти n-й узел с конца за один проход». Это демонстрирует структурированное мышление.
Быстрая проверка
Проверьте понимание концепций «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы узнали, что объединение двух отсортированных списков использует фиктивную голову и сравнение на каждом шаге, занимая O(n+m) времени и O(1) памяти, разделение по середине использует медленный и быстрый указатели, причём быстрый останавливается на последней допустимой паре, а при поиске n-го узла с конца быстрый указатель продвигается на n+1 шагов вперёд, чтобы медленный оказался у предшественника. Далее Вы создадите стеки и очереди и примените их к классическим задачам с собеседований.
Часто задаваемые вопросы
Урок «Слияние, разделение и поиск с конца» бесплатный?
Да — полный текст урока «Слияние, разделение и поиск с конца» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Слияние, разделение и поиск с конца»?
Объединяйте два отсортированных связных списка за O(n), разделяйте список в середине с помощью медленного и быстрого указателей и находите n-й узел с конца Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Слияние, разделение и поиск с конца»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Класс узла и построение списка
- Разворот связного списка
- Обнаружение циклов алгоритмом Флойда
- Слияние, разделение и поиск с конца