İçeriğe geç

Zincirde döngü

Kolay#fast-slow-pointers#cycle-detection~15 dk

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

Hedef zaman
O(n)
Hedef alan
O(1)

Kodda değil de fikirde mi takıldın? Döngü tespiti bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır