Intersection of Two Linked Lists

Q: İki bağlı listenin kesişimini bulmanın zaman karmaşıklığı nedir?

İki işaretçi ve uzunluk yöntemleri, O(m + k) zamanda ve O(1) ek bellekle çalışır. Listelerden birini bir kümede ya da bir işaretleme dizisinde tutmak da doğrusaldır, ancak o liste için bellek gerektirir. Her düğüm çiftini karşılaştırmak O(m·k) sürer.

KolayBağlı liste İki işaretçi

+10

İki tek yönlü bağlı liste, tek bir düğüm havuzunda bulunuyor. i düğümü next[i] düğümüne bağlanır ve -1 bir listenin sonunu belirtir. A listesi headA düğümünden, B listesi ise headB düğümünden başlar. Düğümler belirli bir sıraya göre saklanmadığından bağlantıları takip edin.

İki liste bir noktada birleşebilir: Bir düğümden itibaren sona kadar aynı düğümler üzerinden devam ederler. Her iki listede de bulunan ilk düğümün indeksini döndürün veya ortak düğümleri yoksa -1 döndürün.

Fonksiyon

getIntersectionNode(next: integer-array, headA: integer, headB: integer) → integer

nextinteger-array: her düğümün bağlantı verdiği düğümün indeksi ya da listedeki son düğüm için -1
headAinteger: Liste A'nın ilk düğümü
headBinteger: B listesinin ilk düğümü
Döndürürinteger: iki listenin paylaştığı ilk düğüm veya -1

Kısıtlar

2 ≤ n ≤ 10⁴; burada n, next uzunluğudur.
Her next[i], -1 ya da 0 ile n-1 arasında bir düğüm indeksidir.
0 ≤ headA, headB ≤ n-1 ve headA ≠ headB.
Her iki liste de bir düğümü iki kez ziyaret etmeden -1 noktasında sona erer. Döngü yoktur.
Her düğüm A listesinde, B listesinde veya her iki listededir.

Örnekler

Girdi: next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
Çıktı: 1
Açıklama: A, 3, 5, 1, 4, 0 düğümlerini, B ise 2, 1, 4, 0 düğümlerini ziyaret eder. 1 düğümünden itibaren her düğümü paylaşırlar ve A'nın daha önceki hiçbir düğümü B'de bulunmadığından yanıt 1'dir.

Girdi: next = [2, 3, 4, -1, -1]headA = 0headB = 1
Çıktı: -1
Açıklama: A listesi 0, 2, 4 ve B listesi 1, 3. İkisi de ortak bir düğüme değmeden -1 noktasında sona erer, bu nedenle yanıt -1 olur.

Girdi: next = [3, 2, 0, -1]headA = 1headB = 0
Çıktı: 0
Açıklama: A listesi 1, 2, 0, 3, B listesi ise 0, 3. B listesi, A listesinin son kısmıdır; bu nedenle paylaşılan ilk düğüm doğrudan headB, yani 0 düğümüdür.

Ek soru

O(m + k) sürede ve O(1) ek bellek kullanarak düğümü bulabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bir düğümün bir next'i vardır, bu nedenle kesişen iki liste bir daha ayrılmaz. Özel başlangıçları ortak bir kuyruğa bağlanan bir Y oluştururlar ve cevap birleşme noktasıdır. Başlangıçların uzunlukları farklı olabilir, bu yüzden iki listeyi birlikte ilerletmek birleşme noktasını bulmayı sağlamaz. Aşağıda, m ve k A ve B'nin uzunluklarıdır.

A'nın her düğümünü B'nin tüm düğümleriyle karşılaştır

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Bir işaretçi bir düğüm indeksidir ve ileri gitmek node = next[node] şeklindedir. A listesindeki her a düğümü için sırayla B listesinin tamamını dolaş ve her düğümü a ile karşılaştır. Eşleşen ilk a yanıttır, çünkü A listesindeki daha önceki her düğüm zaten eşleşmemiştir. A listesindeki her düğüm için B listesini yeniden tarar: her listede 5000 düğüm varsa ve ortak düğüm yoksa 2.5 × 10^7 karşılaştırma yapılır.

Algoritma

a = headA olarak ayarla.
a, -1 olmadığı sürece b'yi headB'den -1'e kadar ilerlet.
Herhangi bir noktada b == a ise a'yı döndür.
Aksi hâlde a = next[a] olarak ilerlet ve tekrarla.
A listesi tükenirse -1 döndür.

def getIntersectionNode(next, headA, headB):
    a = headA
    while a != -1:
        # Is node a also on list B? Walk all of B to find out.
        b = headB
        while b != -1:
            if a == b:
                return a
            b = next[b]
        a = next[a]
    return -1

Liste B'nin düğümlerini işaretle

Sezgi

Her düğüm için bir kez “bu düğüm B'de mi?” sorusunu yanıtla: B boyunca ilerle ve her düğümü, boyutu n olan bir boole dizisinde işaretle. Düğüm indeksleri küçük tam sayılar olduğundan, bir dizi hash kümesi işini görür. Ardından A'yı başından başlayarak dolaş. İşaretli ilk düğüm her iki listede de bulunur ve A'yı sırayla dolaştığın için bu, bulunan ilk böyle düğümdür. İlk örnekte B, 2, 1, 4, 0 düğümlerini işaretler ve A boyunca yapılan dolaşım, 1'de durmadan önce 3 ve 5 düğümlerinden geçer. Her liste bir kez dolaşıldığından, n işaret kullanma karşılığında zaman karmaşıklığı O(m + k) olur.

Algoritma

n adet false değerine ayarlanmış boole değeri içeren bir onB dizisi oluştur.
B listesini headB noktasından başlayarak dolaş ve her düğüm için onB[node] = true olarak ayarla.
A listesini headA noktasından başlayarak dolaş. onB[node] değeri true olan ilk düğümü döndür.
A listesi sona ererse -1 döndür.

def getIntersectionNode(next, headA, headB):
    # Mark every node of list B.
    on_b = [False] * len(next)
    node = headB
    while node != -1:
        on_b[node] = True
        node = next[node]
    # The first marked node on list A is the meeting point.
    node = headA
    while node != -1:
        if on_b[node]:
            return node
        node = next[node]
    return -1

Listeleri değiştiren iki işaretçi

Sezgi

Her listeyi birleşme noktasında ayır: A, önce x özel düğüm, ardından c ortak düğüm içerir; B ise önce y özel düğüm, ardından aynı c düğümü içerir. a işaretçisi A boyunca ilerler, -1 düğümüne geçer, sonra headB noktasından yeniden başlar ve x + c + 1 + y adım sonra birleşme noktasına ikinci kez ulaşır. b işaretçisi B boyunca, ardından A boyunca ilerler ve y + c + 1 + x adım sonra ulaşır. Toplamlar eşittir. İlk örnekte x = 2, y = 1 ve c = 3 değerlerindedir ve ikisi de yedi adım sonra 1 düğümünde durur.

Ortak kuyruk yoksa, her iki işaretçi de m + 1 + k adım sonra -1 üzerinde durur (m = k olduğunda m adım sonra) ve döngü -1 değerini döndürür. Bu ortak durma noktası, her işaretçinin geçiş yapmadan önce -1 düğümüne adım atmasının nedenidir. Her işaretçi en fazla m + k + 1 kez ilerler ve iki indekslik bellek kullanır.

Algoritma

a = headA ve b = headB olarak ayarla.
a != b olduğu sürece: a değeri -1 ise headB'ye, değilse next[a]'ya ilerlet.
Aynı turda, b değeri -1 ise headA'ya, değilse next[b]'ye ilerlet.
Döngü sona erdiğinde a'yı döndür. Bu, ortak ilk düğümdür veya -1'dir.

def getIntersectionNode(next, headA, headB):
    a, b = headA, headB
    # Each pointer walks its own list, then the other one. Both cover
    # the same number of nodes, so they reach the meeting node together,
    # or reach -1 together when there is none.
    while a != b:
        a = headB if a == -1 else next[a]
        b = headA if b == -1 else next[b]
    return a

Tuzaklar ve uç durumlar

Son düğümden doğrudan diğer başa geçmek ve -1 noktasında durmayı atlamak. Listelerin ortak hiçbir şeyi olmadığında, işaretçiler hiçbir zaman aynı değeri taşımaz ve döngü sonsuza kadar çalışır.
Bir işaretçiyi kendi başında yeniden başlatmak. Her işaretçi kendi listesinde tur atar ve yalnızca turları denk geldiğinde buluşurlar; bu da (m + 1)·(k + 1) hamleye kadar sürebilir.
Dizi sırasını liste sırası olarak kabul etmek. 0 düğümü yalnızca headA veya headB öyle belirtiyorsa bir baştır ve dizide yan yana olan öğeler bir listede komşu değildir.
Lua ve R'de dizilerin 1'den başladığını unutmak. Düğüm indekslerini 0 tabanlı tutun ve next[node + 1] okuyun.

Sıkça sorulan sorular3

İki bağlı listenin fazladan bellek kullanmadan nerede kesiştiğini nasıl bulursunuz?

İki işaretçi kullanın. Her biri kendi listesinde ilerler ve sonu geçtikten sonra diğer listenin başından devam eder. İkisi de aynı toplam mesafeyi yürüdüğünden, ilk ortak düğüme aynı anda ulaşırlar; ortak düğüm yoksa birlikte sona ulaşırlar.

Listelerin uzunluklarını karşılaştırarak kesişimi bulabilir misin?

Evet. Her iki listenin düğümlerini sayın, daha uzun listedeki işaretçiyi fark kadar ilerletin, ardından eşit olana kadar ikisini de her seferinde bir adım ilerletin. Bu da O(m + k) zaman ve O(1) bellek gerektirir; geçiş yöntemi, iki sayma turuna gerek kalmadan aynı hizalamayı sağlar.

İki bağlı listenin kesişimini bulmanın zaman karmaşıklığı nedir?

İki işaretçi ve uzunluk yöntemleri, O(m + k) zamanda ve O(1) ek bellekle çalışır. Listelerden birini bir kümede ya da bir işaretleme dizisinde tutmak da doğrusaldır, ancak o liste için bellek gerektirir. Her düğüm çiftini karşılaştırmak O(m·k) sürer.

def getIntersectionNode(next, headA, headB):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

next = [-1, 4, 1, 5, 0, 1]
headA = 3
headB = 2

Beklenen Çıktı

Intersection of Two Linked Lists

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

A'nın her düğümünü B'nin tüm düğümleriyle karşılaştır

Liste B'nin düğümlerini işaretle

Listeleri değiştiren iki işaretçi

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler