Dev Easy Notes

Вы накидали много огоньков (кажется ни один пост столько не набирал), а это значит, что придется делать разбор задачи. Ну что ж, погнали, поиск цикла в связном списке.

Условия задачи: есть связный список, и нужно понять, есть ли в нем цикл. Цикл — это когда у нас последний элемент списка ссылается не на null, а на какой-то из элементов этого самого списка, короче, смотрите картинку.

Начну с того, что я вообще не ебу, где такое можно применять. Я понимаю алгоритм поиска цикла в графе, который применяется повсеместно, но в связном списке... Цикл в связном списке — это баг реализации, но да ладно.

Сложность тут в том, что его не решишь обычными способами вроде "запомнить все элементы в set и потом проверять по нему". В этом списке нет индексов, элементы могут повторяться, и мы заранее не знаем, где его конец.

Поэтому поступаем изящнее – два указателя. Один нормальный, который идет по элементам, второй в жопу ужаленный, который скачет через элемент. Если запустить два этих указателя, то у нас может быть два кейса:

👉 быстрый указатель упрется в null – цикла нет
👉 они встретятся на каком-то из элементов – цикл есть

Это собственно все... Код решения на python:

class ListNode:
    def __init__(self, x, next):
        self.val = x
        self.next = next
        
def detect_cycle(head: ListNode) -> bool:
    fast = slow = head
    circle_detected = False
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            circle_detected = True
            break
    return circle_detected

В некоторых случаях могут попросить вернуть ссылку на начало цикла, в этом случае вам нужно будет подвигать ссылку head до нужного места.

www.tgoop.com/dev_easy_notes/402

3.2K viewsedited  Apr 2 at 09:26

Вы накидали много огоньков (кажется ни один пост столько не набирал), а это значит, что придется делать разбор задачи. Ну что ж, погнали, поиск цикла в связном списке.

Условия задачи: есть связный список, и нужно понять, есть ли в нем цикл. Цикл — это когда у нас последний элемент списка ссылается не на null, а на какой-то из элементов этого самого списка, короче, смотрите картинку.

Начну с того, что я вообще не ебу, где такое можно применять. Я понимаю алгоритм поиска цикла в графе, который применяется повсеместно, но в связном списке... Цикл в связном списке — это баг реализации, но да ладно.

Сложность тут в том, что его не решишь обычными способами вроде "запомнить все элементы в set и потом проверять по нему". В этом списке нет индексов, элементы могут повторяться, и мы заранее не знаем, где его конец.

Поэтому поступаем изящнее – два указателя. Один нормальный, который идет по элементам, второй в жопу ужаленный, который скачет через элемент. Если запустить два этих указателя, то у нас может быть два кейса:

👉 быстрый указатель упрется в null – цикла нет
👉 они встретятся на каком-то из элементов – цикл есть

Это собственно все... Код решения на python:

class ListNode:
    def __init__(self, x, next):
        self.val = x
        self.next = next
        
def detect_cycle(head: ListNode) -> bool:
    fast = slow = head
    circle_detected = False
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            circle_detected = True
            break
    return circle_detected

BY Dev Easy Notes