Middle of the Linked List
Kamu mendapatkan singly linked list yang disimpan dalam dua array dengan panjang yang sama. Node i menyimpan nilai values[i] dan terhubung ke node next[i], -1 menandai akhir list, dan head adalah node 0. Node-node tidak disimpan sesuai urutan list, jadi ikuti tautannya.
Kembalikan nilai node tengah. Jika list memiliki jumlah node genap, ada dua node tengah. Kembalikan nilai node kedua.
Fungsi
- valuesinteger-array
- nilai yang disimpan oleh setiap node
- nextinteger-array
- indeks node yang ditautkan oleh setiap node, atau -1 untuk node terakhir
- Mengembalikaninteger
- nilai node tengah, yaitu node tengah kedua saat panjangnya genap
Batasan
1 ≤ n ≤ 5000, dengannsebagai panjangvaluesdannext.-104 ≤ values[i] ≤ 104- Setiap
next[i]adalah-1atau indeks simpul dari0hinggan-1. - Mulai dari node
0, list mengunjungi setiap node tepat satu kali, lalu mencapai-1. Tidak ada siklus.
Contoh
- Input
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- Output
- 5
- Penjelasan
- Dengan mengikuti tautan dari node
0, kamu mengunjungi node0, 3, 4, 2, 1, yang nilainya adalah4, 7, 5, 2, 9. Bagian tengahnya adalah node4, dengan nilai5, bukan entri tengah arrayvalues[2] = 2.
- Input
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- Output
- 40
- Penjelasan
- Di sini node disimpan secara berurutan. Enam node memiliki dua node tengah,
30dan40, dan yang kedua yang dipilih.
- Input
- values = [8]next = [-1]
- Output
- 8
- Penjelasan
- List yang terdiri dari satu node memiliki bagian tengah pada node itu sendiri.
Pertanyaan lanjutan
Bisakah kamu mengembalikan node yang berada sepertiga dari awal list dalam satu kali lintasan? Seberapa cepat masing-masing pointer bergerak, dan di mana kamu akan berhenti?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Kamu tidak mengetahui panjang list sampai mencapai ujungnya. Bagaimana jika dua pejalan mulai dari awal dan salah satunya bergerak dua kali lebih cepat daripada yang lain?
Ketika pejalan yang lebih cepat telah mencapai ujung, pejalan yang lebih lambat telah menempuh setengah jarak, sehingga posisinya berada di node tengah. Satu-satunya hal yang perlu ditentukan adalah kapan harus berhenti agar jumlah node genap membuatnya berada di node tengah kedua.
Mulai
slowdanfastdi node0. Selamafastbukan-1dannext[fast]bukan-1, gerakkan slow satu tautan dan fast dua tautan. Lalu kembalikanvalues[slow].
Solusi
linked list tidak memiliki indeks: kamu hanya mengetahui panjangnya setelah berjalan sampai akhir, melewati bagian tengah. Kamu bisa menyalinnya ke array, atau menghitungnya terlebih dahulu lalu berjalan lagi. Dua pointer dengan kecepatan berbeda hanya memerlukan satu kali lintasan: pointer yang lambat berada di tengah saat pointer yang cepat kehabisan langkah.
Salin nilai-nilai ke dalam array
Intuisi
Telusuri list sekali dan tambahkan setiap nilai ke array: [4, 7, 5, 2, 9] pada contoh pertama. Array menyimpan nilai sesuai urutan dalam list, jadi nilai tengahnya berada pada indeks length / 2 dengan pembagian bilangan bulat. Untuk panjang genap, itu adalah nilai tengah kedua: enam nilai menghasilkan indeks 3, yaitu 40 pada contoh kedua. Penelusuran ini membutuhkan waktu O(n), dan penyalinan membutuhkan memori tambahan O(n).
Algoritma
- Mulai dengan array kosong dan
node = 0. - Selama
nodebukan-1, tambahkanvalues[node]dan lanjutkan kenext[node]. - Kembalikan entri pada indeks
length / 2, dibulatkan ke bawah.
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]Hitung, lalu berjalan setengah jalan
Intuisi
Kamu hanya memerlukan panjangnya, bukan salinannya. Hitung node, kembali ke head, lalu tempuh length / 2 langkah, dibulatkan ke bawah. Setelah k langkah, kamu berada di posisi k, dengan head dihitung sebagai 0, dan length / 2 adalah bagian tengah: posisi 2 dari 5, dan posisi tengah kedua, yaitu posisi 3, dari 6. Pada contoh pertama, kamu menghitung 5, melangkah 0 → 3 → 4, lalu membaca values[4] = 5.
Penggunaan memori turun menjadi O(1). Biayanya adalah perjalanan kedua sepanjang setengah list, total 1.5n langkah.
Algoritma
- Berjalanlah dari node
0ke-1dan hitung jumlah node. - Kembali ke node
0. - Jalankan
node = next[node]tepatcount / 2kali, dibulatkan ke bawah. - Kembalikan
values[node].
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]Pointer cepat dan lambat
Intuisi
Setiap putaran, slow bergerak satu node dan fast bergerak dua node, jadi setelah k putaran, slow berada di posisi k dan fast di posisi 2k. Saat fast mencapai akhir, slow berada di tengah, dan kamu tidak perlu mengetahui panjangnya.
Aturan berhenti menentukan titik tengah mana yang kamu dapatkan. Lakukan perulangan selama fast != -1 dan next[fast] != -1. Untuk panjang ganjil, fast berhenti di node terakhir. Untuk panjang genap, fast melangkah hingga -1, sehingga slow bergerak satu node lebih jauh dan sampai di titik tengah kedua. Dalam contoh kedua, slow bergerak 0, 1, 2, 3, sedangkan fast bergerak 0, 2, 4, -1, jadi jawabannya adalah values[3] = 40. Algoritma ini hanya memerlukan satu kali penelusuran dan dua bilangan bulat di memori.
Algoritma
- Tetapkan
slow = 0danfast = 0. - Selama
fast != -1dannext[fast] != -1, tetapkanslow = next[slow]danfast = next[next[fast]]. - Kembalikan
values[slow].
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
Jebakan dan kasus tepi
- Mengembalikan
values[n / 2]. Node tidak disimpan sesuai urutan list, jadi pada contoh pertama hasilnya2, bukan5. - Mendapatkan node tengah pertama saat panjangnya genap. Perulangan yang berjalan selama
next[fast]dannext[next[fast]]keduanya masih valid berhenti satu putaran terlalu awal dan mengembalikan30, bukan40, pada contoh kedua. - Memeriksa
next[fast]sebelumfast != -1. Saat panjangnya genap, fast menjadi-1, dan membacanext[-1]menyebabkan crash di sebagian besar bahasa. Di Python, operasi itu diam-diam membaca entri terakhir. - Berjalan sebanyak
count / 2 - 1langkah, atau membulatkan ke atas, dalam pendekatan penghitungan. Hitung head sebagai posisi0.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu dan ruang untuk menemukan bagian tengah dari linked list?
Ketiga pendekatan membutuhkan waktu O(n), karena kamu harus menelusuri setidaknya setengah dari list. Menyalin nilai membutuhkan memori tambahan O(n). Menghitung terlebih dahulu serta pointer cepat dan lambat sama-sama menggunakan O(1), dan pointer hanya memerlukan satu kali penelusuran.
Bagaimana cara mengembalikan node tengah pertama, bukan yang kedua?
Ubah aturan berhentinya agar pointer cepat berhenti satu putaran lebih awal: lakukan perulangan selama next[fast] != -1 dan next[next[fast]] != -1. Untuk enam node, pointer lambat lalu berhenti di posisi 2, bukan 3. Dalam pendekatan penghitungan, tempuh (count - 1) / 2 langkah, bukan count / 2.
Di mana lagi teknik pointer cepat dan lambat digunakan?
Dua kecepatan yang sama dapat mendeteksi siklus dalam linked list: dalam sebuah perulangan, pointer cepat mengitari pointer lambat hingga keduanya bertemu. Keduanya juga dapat menemukan titik awal siklus dan membagi list menjadi dua bagian untuk merge sort atau untuk memeriksa apakah list terbaca sama dari kedua arah.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def middleNode(values, next):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
Output yang diharapkan
5