Zincirde döngü
Görev tanımı
Problem
Tek yönlü bağlı bir düğüm zincirinin head'ini alıyorsun. Bir yerde bir düğüm önceki bir düğüme geri bağlanıyor olabilir; bu da dolaşmanın sona ulaşmak yerine sonsuza kadar dönmesine yol açar. Zincir böyle bir döngü içeriyorsa True, bağlantıları izlemek eninde sonunda None'a ulaşıyorsa False döndür. Örneklerde zincir değerleri artı pos ile tarif ediliyor: pos son düğümün geri bağlandığı indeks, döngü yoksa -1.
Örnekler
Input: values = [3, 2, 0, -4], pos = 1
Output: True
Neden: son düğüm 2'yi tutan düğüme geri bağlanıyor
Input: values = [1, 2], pos = -1
Output: False
Neden: dolaşma ikinci düğümden sonra bitiyor
Input: values = [7], pos = 0
Output: True
Neden: edge case: kendini gösteren tek bir düğüm
İpuçları
0 / 3
Ziyaret ettiğin her düğümü hatırlamak işe yarar, ama bütün zincir kadar bellek ister. Hiçbir şey saklamadan bir döngüyü fark etmenin yolu var mı?
Biri diğerinden iki kat hızlı iki koşucuyu bir pistte düşün. Düz bir yolda bir daha asla karşılaşmazlar; dairesel bir pistte karşılaşmak zorundalar.
Bir pointer'ı her seferinde bir adım, diğerini iki adım ilerlet. Hızlı olan sondan düşerse döngü yoktur; ikisi bir gün aynı düğüme inerse vardır.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Çözüm
İki pointer head'den başlar; biri adım başına bir bağlantı, diğeri iki bağlantı ilerler. Döngü yoksa hızlı pointer sona ulaşır ve cevap False olur. Döngü varsa iki pointer da eninde sonunda onun içinde döner ve aralarındaki boşluk her adımda bir bağlantı küçüldüğü için hızlı pointer tam olarak yavaş olanın üzerine inmek zorundadır. Zaman O(n), alan O(1).
class Node:
def __init__(self, val): self.val, self.next = val, None
def build(values, pos): # the tail links back to index pos, or nowhere if -1
nodes = [Node(v) for v in values]
for a, b in zip(nodes, nodes[1:]): a.next = b
if nodes and pos >= 0: nodes[-1].next = nodes[pos]
return nodes[0] if nodes else None
def has_loop(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next # the gap closes by one link per step
if slow is fast:
return True
return False # the fast pointer found the end
print(has_loop(build([3, 2, 0, -4], 1))) # -> True
print(has_loop(build([1, 2], -1))) # -> False
print(has_loop(build([7], 0))) # -> TrueKodda değil de fikirde mi takıldın? Döngü tespiti bunu anlatıyor.