Постановка задачи:

Дан связанный список из N узлов, который может содержать цикл.

Цикл здесь означает, что последний узел списка ссылок соединен с узлом в позиции X.

Удалите цикл из связанного списка, если он присутствует.

Пример:

Input:
N = 3
value[] = {1,3,4}

Output: 1
Explanation: The linked list looks like
1 -> 3 -> 4
     ^    |
     |____|    
A loop is present.

Просто удалите цикл из списка (если он есть), не отключая ни одного узла из списка.

Ожидаемая временная сложность: O(N)
Ожидаемое вспомогательное пространство:O(1)

Спрашивали в следующих компаниях:

Adobe, Amazon, Goldman Sachs, MakeMyTrip, Microsoft, Morgan Stanley, Oracle, Snapdeal, VMWare, Walmart

Подход грубой силы:

Ключевая идея состоит в том, чтобы определить, присутствует ли петля или нет, если она присутствует, нам нужно разорвать петлю.

А. Использование хеширования

  1. Пройдите по связанному списку, поддерживая 2 указателя — текущий и предыдущий.
  2. Используйте HashSet для отслеживания узлов.
  3. Если текущего узла нет в наборе, мы его добавим.
  4. Если текущий узел существует в наборе, это означает, что мы обнаружили петлю.
  5. Установите следующий указатель предыдущего узла в NULL, таким образом, цикл прерывается.

Анализ сложности:

Временная сложность: O(n).
n — общее количество узлов в связанном списке.

Вспомогательное пространство: O(n).
Использование дополнительной структуры данных Set.

B. Оптимальное решение — использование алгоритма обнаружения циклов Флойда

В этом решении мы будем использовать этот алгоритм и с его помощью научимся решать 3 типа вопросов:

  1. Обнаружение цикла в связанном списке.
  2. Найдите длину цикла в связанном списке.
  3. Удалить цикл в связанном списке.

Что такое алгоритм обнаружения цикла Флойда?

Алгоритм обнаружения циклов Флойда поддерживает два указателя, причем первый указатель движется со скоростью, в два раза превышающей скорость второго указателя. Если оба указателя встречаются в какой-то точке, в списке находится цикл.

Пошаговый подход:

  1. Во-первых, нам нужно определить, существует ли цикл, если он есть, мы будем использовать вспомогательную функцию.
  2. Внутри вспомогательной функции мы вычислим длину цикла, допустим, длина цикла = k.
  3. Далее нам нужно узнать начальный узел петли. Если мы это сделаем, то узел перед начальным узлом должен быть установлен в NULL, чтобы разорвать цикл.
  4. Инициализируйте 2 указателя — ptr1 и ptr2 на начало. Переместите указатель ptr2 на k раз вперед, в то время как указатель ptr1 все еще находится в начале.
  5. Запустите цикл, чтобы, если ptr1 и ptr2 встретились, это был начальный узел цикла.
  6. Наконец, мы находим предыдущий узел для начального узла цикла и делаем так, чтобы последний узел указывал на NULL.

Код:

Анализ сложности:

Временная сложность: O(n).
n — общее количество узлов в связанном списке.

Вспомогательный пробел: O(1).

Если вам понравилась эта статья, несколько раз нажмите кнопку "хлопать".

Дает мне достаточную мотивацию, чтобы публиковать больше подобного контента. Поделитесь ею с другом, которому, по вашему мнению, эта статья может помочь.

Свяжитесь со мной — Варша Дас | ЛинкедИн

Спасибо за прочтение.

Удачного кодирования😁