Aradaki mesafe ve buluşma

İki işaretçinin hızları aynı, başlangıçları farklı da olabilir. Sondan k'inci düğümü bulmak için önce birini k adım ileri gönder, sonra ikisini birlikte yürüt. Öndeki sona vardığında, arkadaki tam k adım geride, yani aradığın düğümdedir.

1lead = head
2for _ in range(k):
3    lead = lead.next
4trail = head
5while lead is not None:
6    lead = lead.next
7    trail = trail.next
8return trail

Aradaki mesafe hiç değişmez; değişen yalnızca ikisinin birlikte ne kadar ilerlediğidir. Uzunluğu ölçmek için ayrı bir geçişe gerek kalmaz.

Hızlar farklıysa başka bir şey öğrenirsin: zincirde döngü var mı? Döngü yoksa hızlı işaretçi sona varır ve biter. Döngü varsa hızlı olan içeride dönüp durur ve yavaşa arkadan yetişir: iki işaretçi aynı düğümde buluşur. Görülen düğümleri bir kümede tutmaya gerek kalmaz.

Görevler