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

Условия задачи: есть связный список, и нужно понять, есть ли в нем цикл. Цикл — это когда у нас последний элемент списка ссылается не на 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 до нужного места.
🗿21👍12🔥1



tgoop.com/dev_easy_notes/402
Create:
Last Update:

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

Условия задачи: есть связный список, и нужно понять, есть ли в нем цикл. Цикл — это когда у нас последний элемент списка ссылается не на 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 до нужного места.

BY Dev Easy Notes




Share with your friend now:
tgoop.com/dev_easy_notes/402

View MORE
Open in Telegram


Telegram News

Date: |

Matt Hussey, editorial director of NEAR Protocol (and former editor-in-chief of Decrypt) responded to the news of the Telegram group with “#meIRL.” Telegram offers a powerful toolset that allows businesses to create and manage channels, groups, and bots to broadcast messages, engage in conversations, and offer reliable customer support via bots. Telegram message that reads: "Bear Market Screaming Therapy Group. You are only allowed to send screaming voice notes. Everything else = BAN. Text pics, videos, stickers, gif = BAN. Anything other than screaming = BAN. You think you are smart = BAN. Ng Man-ho, a 27-year-old computer technician, was convicted last month of seven counts of incitement charges after he made use of the 100,000-member Chinese-language channel that he runs and manages to post "seditious messages," which had been shut down since August 2020. But a Telegram statement also said: "Any requests related to political censorship or limiting human rights such as the rights to free speech or assembly are not and will not be considered."
from us


Telegram Dev Easy Notes
FROM American