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: |

Commenting about the court's concerns about the spread of false information related to the elections, Minister Fachin noted Brazil is "facing circumstances that could put Brazil's democracy at risk." During the meeting, the information technology secretary at the TSE, Julio Valente, put forward a list of requests the court believes will disinformation. Add the logo from your device. Adjust the visible area of your image. Congratulations! Now your Telegram channel has a face Click “Save”.! The court said the defendant had also incited people to commit public nuisance, with messages calling on them to take part in rallies and demonstrations including at Hong Kong International Airport, to block roads and to paralyse the public transportation system. Various forms of protest promoted on the messaging platform included general strikes, lunchtime protests and silent sit-ins. Telegram desktop app: In the upper left corner, click the Menu icon (the one with three lines). Select “New Channel” from the drop-down menu. 3How to create a Telegram channel?
from us


Telegram Dev Easy Notes
FROM American