Menggabungkan, Memisahkan, dan Menemukan Elemen ke-N dari Akhir
Gabungkan dua linked list terurut dalam O(n), pisahkan list di titik tengah menggunakan pointer lambat-cepat, dan temukan node ke-n dari ekor.
Menggabungkan, Memisahkan, dan Menemukan Elemen ke-N dari Akhir adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Tiga Pola Penting Daftar Tertaut
Pelajaran ini membahas tiga operasi dasar daftar tertaut yang terus-menerus muncul sebagai blok penyusun dalam soal yang lebih sulit: menggabungkan dua daftar terurut (digunakan dalam pengurutan gabung dan penggabungan K-arah), memisahkan daftar di titik tengahnya (digunakan dalam pengurutan gabung dan deteksi palindrom), serta menemukan simpul ke-n dari akhir (digunakan untuk menghapus simpul ke-n dari akhir).
Ketiganya mengandalkan teknik yang telah Anda lihat: simpul kepala semu, penunjuk lambat-cepat, dan pelacakan batas yang cermat.
Menggabungkan Dua Daftar Terurut
LeetCode 21 'Menggabungkan Dua Daftar Terurut': diberikan dua daftar tertaut terurut, kembalikan satu daftar terurut hasil penggabungan. Gunakan kepala semu dan penunjuk ekor curr. Pada setiap langkah, bandingkan kepala kedua daftar dan tautkan simpul yang lebih kecil ke curr. Ketika salah satu daftar habis, tautkan sisa daftar lainnya. Waktu: O(n+m), Ruang: O(1) (penyambungan ulang di tempat).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2 # attach remaining nodes
return dummy.next
def build(arr):
d = ListNode(); c = d
for v in arr:
c.next = ListNode(v); c = c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))Melacak Langkah Penggabungan
Lacak mergeTwoLists([1,2,4], [1,3,4]): bandingkan 1 dan 1—pilih 1 dari daftar pertama, majukan daftar pertama ke 2. Bandingkan 2 dan 1—pilih 1 dari daftar kedua, majukan daftar kedua ke 3. Bandingkan 2 dan 3—pilih 2 dari daftar pertama, majukan daftar pertama ke 4. Bandingkan 4 dan 3—pilih 3 dari daftar kedua, majukan daftar kedua ke 4. Bandingkan 4 dan 4—pilih 4 dari daftar pertama, majukan daftar pertama ke None. Tambahkan 4 yang tersisa dari daftar kedua. Hasil: [1,1,2,3,4,4].
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
step = 0
while l1 and l2:
step += 1
if l1.val <= l2.val:
print(f'Step {step}: pick l1({l1.val})')
curr.next = l1; l1 = l1.next
else:
print(f'Step {step}: pick l2({l2.val})')
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
mergeTwoLists(build([1,2,4]),build([1,3,4]))Menemukan Titik Tengah dengan Penunjuk Lambat-Cepat
Untuk memisahkan daftar di titik tengahnya, gunakan pola penunjuk lambat-cepat. slow maju 1 langkah; fast maju 2 langkah. Ketika fast mencapai None (atau simpul terakhir), slow berada di titik tengah. Untuk daftar dengan panjang genap, cara ini menghasilkan simpul tengah pertama dari dua simpul tengah, yang merupakan konvensi untuk pemisahan dalam pengurutan gabung.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_at_mid(head):
'''Returns (first_half_head, second_half_head).'''
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # second half starts here
slow.next = None # sever the list
return head, mid
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second)) # [1,2,3] [4,5]Pengurutan Gabung pada Daftar Tertaut
LeetCode 148 'Urutkan Daftar': urutkan daftar tertaut dalam waktu O(n log n) dan ruang O(log n). Pendekatannya: bagi daftar pada titik tengah, urutkan setiap paruh secara rekursif, lalu gabungkan. Pengurutan gabung pada daftar tertaut merupakan pendekatan alami karena pembagian pada titik tengah memerlukan O(n) (bukan O(1) seperti pada larik), tetapi kompleksitas keseluruhannya tetap O(n log n) dengan hanya memerlukan ruang tumpukan O(log n).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(head):
if not head or not head.next:
return head
# Split
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# Recurse
left = sortList(head)
right = sortList(mid)
# Merge
dummy = ListNode(0)
curr = dummy
while left and right:
if left.val <= right.val:
curr.next = left; left = left.next
else:
curr.next = right; right = right.next
curr = curr.next
curr.next = left or right
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(sortList(build([4,2,1,3])))) # [1,2,3,4]Menemukan Simpul ke-N dari Akhir
LeetCode 19 'Hapus Simpul ke-N dari Akhir Daftar': temukan simpul ke-n dari akhir dalam satu kali penelusuran. Gunakan dua penunjuk yang dipisahkan tepat oleh n simpul. Majukan fast n langkah lebih dahulu daripada slow. Kemudian majukan keduanya bersama-sama hingga fast mencapai simpul terakhir. Pada saat itu, slow berada di simpul ke-(n+1) dari akhir — yaitu simpul pendahulu dari simpul yang akan dihapus.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = dummy
for _ in range(n + 1): # advance fast n+1 steps
fast = fast.next
slow = dummy
while fast: # advance both until fast is None
slow = slow.next
fast = fast.next
slow.next = slow.next.next # remove nth node
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(removeNthFromEnd(build([1,2,3,4,5]), 2))) # [1,2,3,5]Mengapa Diperlukan n+1 Langkah untuk Menghapus Simpul ke-N
Hal yang mudah terlewat adalah memajukan penunjuk cepat sebanyak n+1 langkah (bukan n) dari kepala dummy. Setelah n+1 langkah, penunjuk cepat berada n+1 posisi di depan penunjuk lambat (keduanya dimulai dari dummy). Saat penunjuk cepat mencapai nilai kosong (satu posisi setelah ekor), penunjuk lambat berada n+1 posisi sebelum nilai kosong — artinya penunjuk lambat berada pada posisi (panjang - n - 1) jika dihitung mulai dari nol, atau pada simpul pendahulu target. Dengan demikian, slow.next = slow.next.next dapat menghapus simpul ke-n dari akhir dengan rapi.
# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow) 1 2 3(fast) 4 5 None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')Irisan Dua Daftar Tertaut
LeetCode 160 'Temukan Irisan Dua Daftar Tertaut': temukan simpul tempat dua daftar pertama kali beririsan. Trik dengan ruang O(1): majukan dua penunjuk, masing-masing satu untuk setiap daftar. Saat sebuah penunjuk mencapai akhir, alihkan penunjuk tersebut ke kepala daftar lainnya. Setelah paling banyak panjang A + panjang B langkah, kedua penunjuk telah menempuh jarak total yang sama dan pasti berada pada simpul irisan (atau keduanya berada di akhir jika tidak ada irisan).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a # None if no intersection
# Build: A: 4->1->\ B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val) # 8Menggabungkan K Daftar Terurut (Bagi dan Taklukkan)
LeetCode 23 'Gabungkan K Daftar Terurut': jika diberikan k daftar terurut, gabungkan semuanya menjadi satu daftar. Pendekatan optimalnya adalah berulang kali menggabungkan pasangan daftar menggunakan strategi bagi dan taklukkan, sehingga jumlah daftar menjadi setengah pada setiap putaran. Dengan k daftar yang rata-rata memiliki panjang n, proses ini memerlukan waktu O(n k log k), dibandingkan O(n k²) untuk penggabungan berurutan. Pendekatan heap minimum juga memerlukan O(n k log k).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
def merge_two(l1, l2):
dummy = ListNode(0); curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1; l1 = l1.next
else:
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
if not lists: return None
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i+1 < len(lists) else None
merged.append(merge_two(l1, l2))
lists = merged
return lists[0]
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists))) # [1,1,2,3,4,4,5,6]Daftar Tertaut Ganjil-Genap
LeetCode 328 'Daftar Tertaut Ganjil-Genap': kelompokkan semua simpul berindeks ganjil terlebih dahulu, kemudian simpul berindeks genap (dengan indeks dimulai dari 1). Pendekatannya: pertahankan dua rantai terpisah (ganjil dan genap), lalu hubungkan keduanya setelah selesai. Satu kali penelusuran melalui daftar sudah cukup, sehingga memerlukan waktu O(n) dan ruang O(1). Ini merupakan contoh jelas pemajuan dua penunjuk secara bersamaan dengan langkah yang berbeda.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(oddEvenList(build([1,2,3,4,5])))) # [1,3,5,2,4]Menyatukan Semuanya
Ketiga pola dalam pelajaran ini — menggabungkan daftar terurut, membagi pada titik tengah, dan menemukan simpul ke-n dari akhir — memiliki tema yang sama: gunakan variabel penunjuk tambahan untuk melacak posisi tanpa memerlukan memori tambahan. Kepala dummy menyederhanakan penggabungan dan penghapusan; selisih penunjuk lambat-cepat menetapkan posisi relatif tertentu; dan memajukan satu penunjuk lebih dahulu menciptakan jarak yang diinginkan.
Dalam wawancara, sebutkan pola yang Anda gunakan sebelum mulai menulis kode: 'Saya akan menggunakan teknik selisih dua penunjuk untuk menemukan simpul ke-n dari akhir dalam satu kali penelusuran.' Hal ini menunjukkan pemikiran yang terstruktur.
Pemeriksaan Singkat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda mempelajari: penggabungan dua daftar terurut menggunakan kepala dummy dan perbandingan pada setiap langkah untuk mencapai waktu O(n+m) dan ruang O(1), pembagian pada titik tengah menggunakan penunjuk lambat-cepat dengan penunjuk cepat berhenti pada pasangan valid terakhir, dan pencarian simpul ke-n dari akhir dengan memajukan penunjuk cepat n+1 langkah lebih dahulu agar penunjuk lambat berada pada simpul pendahulu. Selanjutnya kita akan membangun tumpukan dan antrean, lalu menerapkannya pada masalah wawancara klasik.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Menggabungkan, Memisahkan, dan Menemukan Elemen ke-N dari Akhir” gratis?
Ya — teks lengkap “Menggabungkan, Memisahkan, dan Menemukan Elemen ke-N dari Akhir” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Menggabungkan, Memisahkan, dan Menemukan Elemen ke-N dari Akhir”?
Gabungkan dua linked list terurut dalam O(n), pisahkan list di titik tengah menggunakan pointer lambat-cepat, dan temukan node ke-n dari ekor. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Menggabungkan, Memisahkan, dan Menemukan Elemen ke-N dari Akhir” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Kelas Node dan Pembuatan List
- Membalik Linked List
- Deteksi Siklus dengan Algoritma Floyd
- Menggabungkan, Memisahkan, dan Menemukan Elemen ke-N dari Akhir