İki zincir nerede birleşiyor
Görev tanımı
Problem
İki sürüm geçmişi, ortak bir commit'te birleşip oradan sona kadar birlikte ilerleyebilen tek yönlü bağlı listeler (linked list) olarak saklanıyor. İki listenin head'leri verildiğinde, paylaştıkları ilk düğümü döndür; hiç karşılaşmıyorlarsa None döndür. Paylaşmak, yalnız eşit bir değer değil, aynı düğüm nesnesi anlamına gelir. İki listeyi de değiştirme ve yalnız O(1) ek alan kullan. Her listede en fazla 30.000 düğüm var.
Örnekler
Input: a = 4 -> 1 -> 8 -> 4 -> 5, b = 5 -> 6 -> 1 -> 8 -> 4 -> 5,
both lists share the nodes 8 -> 4 -> 5
Output: the node holding 8
Neden: ondan önceki 1 her listede farklı bir düğüm, yalnız değer eşleşiyor
Input: a = 2 -> 6 -> 4, b = 1 -> 5, no shared nodes
Output: None
Input: a = 7, b = 7, where both heads are the same node
Output: the node holding 7
Neden: edge case: listeler her şeyi paylaşıyor, yani cevap head'in kendisi
İpuçları
0 / 3
Bir listenin her düğümünü bir kümede saklayıp diğerini dolaşmak işe yarar, ama O(n) alana mal olur. İki dolaşmayı hizalarsan ortak noktaları ne olur?
Listelerin birleşme noktasından sonraki kısımları özdeştir. Tek sorun iki head'in birleşme noktasına farklı uzaklıklarda durması.
Her listede bir pointer dolaştır. Biri sona ulaşınca onu diğer listenin head'inde yeniden başlat. İkisi de a + b düğüm dolaştıktan sonra birleşme düğümüne, birleşme yoksa da None'a birlikte varır.
- Hedef zaman
- O(m + n)
- Hedef alan
- O(1)
Kısıtlar
- each list has at most 30,000 nodes
Çözüm
a listesinin birleşmeden önce x düğümü, b listesinin y düğümü, ortak son kısmın da z düğümü olsun. a'yı dolaşıp sonra b'ye geçen bir pointer birleşme düğümüne ulaşmadan x + z + y düğüm katar; b'yi sonra a'yı dolaşan bir pointer da y + z + x, yani aynı mesafeyi katar; bu yüzden aynı adımda onun üzerine inerler. Listeler hiç karşılaşmadığında iki pointer da toplam uzunluğu birlikte bitirir ve aynı anda None olur; bu da döngüyü bitirir. Her pointer en fazla a + b adım atar; zaman O(a + b), ek alan O(1).
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
def merge_point(a, b):
p, q = a, b
while p is not q:
p = p.next if p else b # switch to the other list at the end
q = q.next if q else a
return p # the shared node, or None
shared = Node(8, Node(4, Node(5)))
first_a = Node(4, Node(1, shared))
first_b = Node(5, Node(6, Node(1, shared)))
print(merge_point(first_a, first_b).val) # -> 8
print(merge_point(Node(2, Node(6, Node(4))), Node(1, Node(5)))) # -> None
same = Node(7)
print(merge_point(same, same).val) # -> 7Kodda değil de fikirde mi takıldın? Dolaşma ve arama bunu anlatıyor.