İçeriğe geç

İki zincir nerede birleşiyor

Kolay#two-pointers#list-traversal~15 dk

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

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

Kısıtlar

  • each list has at most 30,000 nodes

Kodda değil de fikirde mi takıldın? Dolaşma ve arama bunu anlatıyor.

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