Intersection of Two Linked Lists

Q: Какова временная сложность поиска пересечения двух связных списков?

Оба метода с указателями и длиной работают за время O(m + k) и используют O(1) дополнительной памяти. Запоминание одного списка в множестве или массиве отметок также требует линейного времени, но требует памяти для этого списка. Сравнение каждой пары узлов занимает O(m·k) .

ЛегкоСвязный список Два указателя

+10

Два односвязных списка находятся в одном пуле узлов. Узел i ссылается на узел next[i], а -1 завершает список. Список A начинается с узла headA, а список B — с узла headB. Узлы хранятся в произвольном порядке, поэтому следуйте по ссылкам.

Два списка могут пересекаться: начиная с некоторого узла, они продолжаются через одни и те же узлы до конца. Верните индекс первого узла, который есть в обоих списках, или -1, если у них нет общих узлов.

Функция

getIntersectionNode(next: integer-array, headA: integer, headB: integer) → integer

nextinteger-array: индекс узла, на который ссылается каждый узел, или -1 для последнего узла списка
headAinteger: первый узел списка A
headBinteger: первый узел списка B
Возвращаетinteger: первый узел, общий для двух списков, или -1

Ограничения

2 ≤ n ≤ 10⁴, где n — длина next.
Каждый элемент next[i] равен -1 или индексу узла от 0 до n-1.
0 ≤ headA, headB ≤ n-1 и headA ≠ headB.
Оба списка заканчиваются на -1, не посещая ни один узел дважды. Цикла нет.
Каждый узел находится в списке A, в списке B или в обоих.

Примеры

Ввод: next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
Вывод: 1
Пояснение: A проходит через 3, 5, 1, 4, 0, а B — через 2, 1, 4, 0. Начиная с узла 1, они проходят через все общие узлы, и ни один из более ранних узлов A не встречается у B, поэтому ответ — 1.

Ввод: next = [2, 3, 4, -1, -1]headA = 0headB = 1
Вывод: -1
Пояснение: Список A — это 0, 2, 4, а список B — 1, 3. Оба заканчиваются на -1, не соприкасаясь с общим узлом, поэтому ответ — -1.

Ввод: next = [3, 2, 0, -1]headA = 1headB = 0
Вывод: 0
Пояснение: Список A — это 1, 2, 0, 3, а список B — 0, 3. Список B является хвостом списка A, поэтому первый общий узел — это сам headB, узел 0.

Дополнительный вопрос

Сможешь найти узел за время O(m + k), используя O(1) дополнительной памяти?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

У узла есть один next, поэтому два списка, которые встретились, больше не расходятся. Они образуют Y: два отдельных начала соединяются в общий хвост, а ответ — это место соединения. Начала могут иметь разную длину, поэтому, если двигаться по обоим спискам одновременно, место соединения можно пропустить. Ниже m и k — длины A и B.

Проверьте каждый узел A на соответствие всем узлам B

Верно, но не успевает на самых больших тестах

Идея

Указатель — это индекс узла, а переход вперёд — это node = next[node]. Для каждого узла a списка A по порядку пройдите по всему списку B и сравните каждый узел с a. Первый совпавший a и будет ответом, потому что все предыдущие узлы A уже не подошли. Для каждого узла A список B просматривается заново: если в каждом списке по 5000 узлов и общих узлов нет, потребуется 2.5 × 10^7 сравнений.

Алгоритм

Установи a = headA.
Пока a не равно -1, проходи по b от headB до -1.
Если в какой-либо момент b == a, верни a.
В противном случае перемести a = next[a] и повтори.
Если список A закончится, верни -1.

def getIntersectionNode(next, headA, headB):
    a = headA
    while a != -1:
        # Is node a also on list B? Walk all of B to find out.
        b = headB
        while b != -1:
            if a == b:
                return a
            b = next[b]
        a = next[a]
    return -1

Отметьте узлы списка B

Идея

Для каждого узла один раз ответьте на вопрос «этот узел есть в B?»: пройдите по B и отметьте каждый узел в булевом массиве размера n. Индексы узлов — небольшие целые числа, поэтому для этой задачи достаточно массива вместо хеш-множества. Затем пройдите по A, начиная с его головы. Первый отмеченный узел входит в оба списка, и это первый такой узел, поскольку вы проходите A по порядку. В первом примере B отмечает 2, 1, 4, 0, а при проходе по A сначала встречаются 3 и 5, после чего проход останавливается на 1. Каждый список проходится один раз, поэтому время работы составляет O(m + k) ценой n отметок.

Алгоритм

Создай onB — массив из n логических значений, установленных в false.
Пройди по списку B, начиная с headB, и установи onB[node] = true для каждого узла.
Пройди по списку A, начиная с headA. Верни первый узел, для которого onB[node] имеет значение true.
Если список A закончится, верни -1.

def getIntersectionNode(next, headA, headB):
    # Mark every node of list B.
    on_b = [False] * len(next)
    node = headB
    while node != -1:
        on_b[node] = True
        node = next[node]
    # The first marked node on list A is the meeting point.
    node = headA
    while node != -1:
        if on_b[node]:
            return node
        node = next[node]
    return -1

Два указателя, переключающиеся между списками

Идея

Раздели каждый список в точке соединения: в A сначала идут x собственных узлов, затем c общих, а в B — y собственных узлов, затем те же c общих. Указатель a проходит по A, переходит на -1, затем начинает заново с headB и достигает точки соединения во второй раз после x + c + 1 + y перемещений. Указатель b проходит по B, затем по A и прибывает после y + c + 1 + x перемещений. Общее число перемещений совпадает. В первом примере x = 2, y = 1 и c = 3, и оба указателя оказываются на узле 1 после семи перемещений.

Если общего хвоста нет, оба указателя оказываются на -1 после m + 1 + k перемещений (после m, если m = k), и цикл возвращает -1. Именно поэтому каждый указатель переходит на -1 перед переключением. Каждый указатель перемещается не более m + k + 1 раз, при этом используются два индекса памяти.

Алгоритм

Установи a = headA и b = headB.
Пока a != b: перемещай a к headB, если он равен -1, иначе — к next[a].
В том же раунде перемещай b к headA, если он равен -1, иначе — к next[b].
Когда цикл завершится, верни a. Это первый общий узел или -1.

def getIntersectionNode(next, headA, headB):
    a, b = headA, headB
    # Each pointer walks its own list, then the other one. Both cover
    # the same number of nodes, so they reach the meeting node together,
    # or reach -1 together when there is none.
    while a != b:
        a = headB if a == -1 else next[a]
        b = headA if b == -1 else next[b]
    return a

Ловушки и крайние случаи

Переход от последнего узла сразу к другой голове, пропуская остановку на -1. Если у списков нет общих узлов, указатели никогда не принимают одинаковое значение, и цикл выполняется бесконечно.
Перезапуск указателя с его собственной головы. Каждый указатель затем обходит свой список, и они встречаются только тогда, когда их обходы совпадают, что может занять до (m + 1)·(k + 1) перемещений.
Считать порядок массива порядком списка. Узел 0 является головой, только если это указано в headA или headB, а соседние элементы массива не являются соседними узлами списка.
В Lua и R не забывай, что индексация массивов начинается с 1. Сохраняй индексы узлов с отсчётом от 0 и читай next[node + 1].

Частые вопросы3

Как найти место пересечения двух связных списков без дополнительной памяти?

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

Сможешь найти пересечение, сравнив длины списков?

Да. Подсчитай узлы в обоих списках, перемести указатель в более длинном списке вперёд на разницу, затем перемещай оба указателя по одному шагу, пока они не сравняются. Это также требует O(m + k) времени и O(1) памяти; метод переключения обеспечивает такое же выравнивание без двух проходов подсчёта.

Какова временная сложность поиска пересечения двух связных списков?

Оба метода с указателями и длиной работают за время O(m + k) и используют O(1) дополнительной памяти. Запоминание одного списка в множестве или массиве отметок также требует линейного времени, но требует памяти для этого списка. Сравнение каждой пары узлов занимает O(m·k).

def getIntersectionNode(next, headA, headB):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

next = [-1, 4, 1, 5, 0, 1]
headA = 3
headB = 2

Ожидаемый вывод

Intersection of Two Linked Lists

Функция

Ограничения

Примеры

Подсказки

Решение

Проверьте каждый узел A на соответствие всем узлам B

Отметьте узлы списка B

Два указателя, переключающиеся между списками

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи