Intersection of Two Linked Lists

Q: Apa kompleksitas waktu untuk menemukan irisan dari dua linked list?

Metode dua pointer dan panjang berjalan dalam waktu O(m + k) dengan memori tambahan O(1) . Menyimpan satu list dalam set atau array penanda juga membutuhkan waktu linear, tetapi memerlukan memori untuk list tersebut. Membandingkan setiap pasangan node membutuhkan waktu O(m·k) .

MudahLinked list Two pointers

+10

Dua linked list singly berada dalam satu pool node. Node i terhubung ke node next[i], dan -1 menandai akhir sebuah list. List A dimulai dari node headA dan list B dari node headB. Node-node disimpan tanpa urutan tertentu, jadi ikuti tautannya.

Kedua list dapat bertemu: mulai dari suatu node, keduanya berlanjut melalui node-node yang sama hingga akhir. Kembalikan indeks node pertama yang ada di kedua list, atau -1 jika keduanya tidak memiliki node yang sama.

Fungsi

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

nextinteger-array: indeks node yang ditautkan oleh setiap node, atau -1 untuk node terakhir dalam sebuah list
headAinteger: node pertama dari list A
headBinteger: simpul pertama dari list B
Mengembalikaninteger: simpul pertama yang dimiliki kedua list, atau -1

Batasan

2 ≤ n ≤ 10⁴, dengan n sebagai panjang next.
Setiap next[i] bernilai -1 atau indeks node dari 0 hingga n-1.
0 ≤ headA, headB ≤ n-1 dan headA ≠ headB.
Kedua list berakhir di -1 tanpa mengunjungi node yang sama dua kali. Tidak ada siklus.
Setiap node berada di list A, di list B, atau di keduanya.

Contoh

Input: next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
Output: 1
Penjelasan: A mengunjungi 3, 5, 1, 4, 0 dan B mengunjungi 2, 1, 4, 0. Mulai dari node 1, keduanya berbagi setiap node, dan tidak ada node A sebelumnya yang juga ada di B, jadi jawabannya adalah 1.

Input: next = [2, 3, 4, -1, -1]headA = 0headB = 1
Output: -1
Penjelasan: list A adalah 0, 2, 4 dan list B adalah 1, 3. Keduanya berakhir di -1 tanpa menyentuh node yang sama, jadi jawabannya adalah -1.

Input: next = [3, 2, 0, -1]headA = 1headB = 0
Output: 0
Penjelasan: list A adalah 1, 2, 0, 3 dan list B adalah 0, 3. list B adalah ekor dari list A, jadi simpul pertama yang sama adalah headB itu sendiri, yaitu simpul 0.

Pertanyaan lanjutan

Bisakah kamu menemukan node dalam waktu O(m + k) dengan memori tambahan O(1)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Sebuah node memiliki satu next, jadi dua list yang bertemu tidak akan terpisah lagi. Keduanya membentuk Y, dua awal terpisah yang bergabung menjadi satu bagian akhir, dan jawabannya adalah titik pertemuannya. Panjang kedua bagian awal bisa berbeda, jadi melangkahkan kedua list bersama-sama membuatmu melewatkan titik pertemuan. Di bawah ini, m dan k adalah panjang A dan B.

Periksa setiap simpul A terhadap semua simpul B

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Pointer adalah indeks node, dan untuk bergerak maju gunakan node = next[node]. Untuk setiap node a dari A secara berurutan, telusuri seluruh B dan bandingkan setiap node dengan a. Node a pertama yang cocok adalah jawabannya, karena setiap node A sebelumnya sudah tidak cocok. Cara ini memindai ulang B untuk setiap node A: dengan 5000 node pada setiap list dan tanpa node yang sama, jumlahnya adalah 2.5 × 10^7 perbandingan.

Algoritma

Tetapkan a = headA.
Selama a bukan -1, telusuri b dari headB hingga -1.
Jika b == a pada titik mana pun, kembalikan a.
Jika tidak, pindahkan a = next[a] dan ulangi.
Jika list A habis, kembalikan -1.

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

Tandai simpul-simpul list B

Intuisi

Jawab “apakah node ini ada di B?” sekali untuk setiap node: telusuri B dan tandai setiap node dalam array boolean berukuran n. Indeks node berupa bilangan bulat kecil, jadi array bisa menggantikan set hash. Lalu telusuri A mulai dari head-nya. Node pertama yang ditandai ada di kedua list, dan itulah node pertama karena kamu menelusuri A secara berurutan. Pada contoh pertama, B menandai 2, 1, 4, 0, dan penelusuran sepanjang A melewati 3 dan 5 sebelum berhenti di 1. Setiap list ditelusuri sekali, sehingga waktunya O(m + k), dengan biaya n penanda.

Algoritma

Buat onB, sebuah array berisi n nilai boolean yang ditetapkan ke false.
Telusuri list B mulai dari headB dan tetapkan onB[node] = true untuk setiap node.
Telusuri list A mulai dari headA. Kembalikan node pertama dengan onB[node] bernilai true.
Jika list A berakhir, kembalikan -1.

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

Dua pointer yang berganti list

Intuisi

Pisahkan setiap list pada titik pertemuan: A memiliki x node privat lalu c node yang dipakai bersama, dan B memiliki y node privat lalu c node yang sama. Pointer a menyusuri A, melangkah ke -1, lalu mulai lagi dari headB, dan mencapai titik pertemuan untuk kedua kalinya setelah x + c + 1 + y langkah. Pointer b menyusuri B, lalu A, dan tiba setelah y + c + 1 + x langkah. Jumlahnya sama. Pada contoh pertama, x = 2, y = 1, dan c = 3, dan keduanya berada di node 1 setelah tujuh langkah.

Jika tidak ada bagian akhir yang dipakai bersama, kedua pointer berada di -1 setelah m + 1 + k langkah (setelah m langkah saat m = k), lalu perulangan mengembalikan -1. Titik berhenti bersama itu menjadi alasan setiap pointer melangkah ke -1 sebelum berpindah. Setiap pointer bergerak paling banyak m + k + 1 kali, dengan penggunaan memori untuk dua indeks.

Algoritma

Tetapkan a = headA dan b = headB.
Selama a != b: pindahkan a ke headB jika nilainya -1, jika tidak, pindahkan ke next[a].
Pada putaran yang sama, pindahkan b ke headA jika nilainya -1, jika tidak, pindahkan ke next[b].
Saat perulangan berakhir, kembalikan a. Nilainya adalah node bersama pertama, atau -1.

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

Jebakan dan kasus tepi

Beralih dari simpul terakhir langsung ke head lainnya, tanpa berhenti di -1. Jika kedua list tidak memiliki simpul yang sama, pointer tidak pernah menyimpan nilai yang sama dan perulangan berjalan tanpa henti.
Memulai ulang pointer di head-nya sendiri. Setiap pointer lalu berputar mengelilingi list-nya sendiri, dan keduanya hanya bertemu saat putarannya sejajar, yang bisa memerlukan hingga (m + 1)·(k + 1) langkah.
Menganggap urutan array sebagai urutan list. Simpul 0 adalah head hanya jika headA atau headB menyatakan demikian, dan simpul yang bersebelahan di array belum tentu bertetangga dalam list.
Di Lua dan R, lupa bahwa array dimulai dari 1. Pertahankan indeks simpul berbasis 0 dan baca next[node + 1].

Pertanyaan yang sering diajukan3

Bagaimana cara menemukan titik perpotongan dua linked list tanpa memori tambahan?

Jalankan dua pointer. Masing-masing menelusuri list-nya sendiri, lalu setelah melewati ujung, melanjutkan dari kepala list yang lain. Keduanya menempuh jarak total yang sama, jadi mereka mencapai node pertama yang sama pada saat bersamaan, atau mencapai ujung bersama-sama jika tidak ada.

Bisakah kamu menemukan irisan dengan membandingkan panjang list?

Ya. Hitung node di kedua list, majukan pointer pada list yang lebih panjang sejauh selisihnya, lalu majukan keduanya satu langkah setiap kali hingga keduanya sama. Metode ini juga membutuhkan waktu O(m + k) dan memori O(1); metode pergantian mendapatkan keselarasan yang sama tanpa dua kali menghitung.

Apa kompleksitas waktu untuk menemukan irisan dari dua linked list?

Metode dua pointer dan panjang berjalan dalam waktu O(m + k) dengan memori tambahan O(1). Menyimpan satu list dalam set atau array penanda juga membutuhkan waktu linear, tetapi memerlukan memori untuk list tersebut. Membandingkan setiap pasangan node membutuhkan waktu O(m·k).

def getIntersectionNode(next, headA, headB):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

Intersection of Two Linked Lists

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Periksa setiap simpul A terhadap semua simpul B

Tandai simpul-simpul list B

Dua pointer yang berganti list

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa