Birleştirme, Bölme ve Sondan N’inciyi Bulma
İki sıralı bağlı listeyi O(n) sürede birleştirin, yavaş-hızlı işaretçilerle listeyi orta noktadan bölün ve sondan n’inci düğümü bulun.
Birleştirme, Bölme ve Sondan N’inciyi Bulma, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Üç Temel Bağlı Liste Kalıbı
Bu derste, daha zor problemlerde yapı taşı olarak sürekli karşınıza çıkan üç temel bağlı liste işlemi ele alınır: iki sıralı listeyi birleştirme (birleştirmeli sıralamada ve K-yollu birleştirmede kullanılır), bir listeyi orta noktasından bölme (birleştirmeli sıralamada ve palindrom algılamada kullanılır) ve sondan n'inci düğümü bulma (sondan n'inci düğümü kaldırma probleminde kullanılır).
Bu üç işlem de daha önce gördüğünüz tekniklere dayanır: sahte baş düğüm, yavaş-hızlı işaretçiler ve sınırların dikkatli biçimde izlenmesi.
İki Sıralı Listeyi Birleştirme
LeetCode 21, 'İki Sıralı Listeyi Birleştirme': iki sıralı bağlı liste verildiğinde tek bir sıralı bağlı liste döndürün. Sahte bir baş düğüm ve bir curr kuyruk işaretçisi kullanın. Her adımda iki listenin başlarını karşılaştırıp küçük olan düğümü curr'a bağlayın. Listelerden biri tükendiğinde diğerinin kalan kısmını bağlayın. Zaman: O(n+m), Alan: O(1) (yerinde yeniden bağlama).
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]))))Birleştirme Adımını Adım Adım İzleme
mergeTwoLists([1,2,4], [1,3,4]) çağrısını izleyelim: 1 ve 1'i karşılaştırın — l1(1)'i seçin, l1'i 2'ye ilerletin. 2 ve 1'i karşılaştırın — l2(1)'i seçin, l2'yi 3'e ilerletin. 2 ve 3'ü karşılaştırın — l1(2)'yi seçin, l1'i 4'e ilerletin. 4 ve 3'ü karşılaştırın — l2(3)'ü seçin, l2'yi 4'e ilerletin. 4 ve 4'ü karşılaştırın — l1(4)'ü seçin, l1'i None'a ilerletin. Kalan l2(4)'ü ekleyin. Sonuç: [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]))Yavaş-Hızlı İşaretçilerle Orta Noktayı Bulma
Bir listeyi orta noktasından bölmek için yavaş-hızlı işaretçi kalıbını kullanın. slow 1 adım, fast ise 2 adım ilerler. fast None değerine (veya son düğüme) ulaştığında slow orta noktadadır. Çift uzunluklu bir listede bu yöntem, iki orta düğümün ilkini verir; birleştirmeli sıralamada bölme işlemi için geleneksel olan da budur.
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]Bağlı Listede Birleştirmeli Sıralama
LeetCode 148 'Listeyi Sırala': bağlı bir listeyi O(n log n) zamanda ve O(log n) alanda sıralayın. Yaklaşım şöyledir: listeyi orta noktadan bölün, her yarıyı özyinelemeli olarak sıralayın ve birleştirin. Bağlı listelerde birleştirmeli sıralama doğaldır; çünkü orta noktadan bölme O(n)'dir (dizilerdeki gibi O(1) değil), ancak toplam karmaşıklık yalnızca O(log n) çağrı yığını alanıyla yine O(n log n)'dir.
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]Sondan N'inci Düğümü Bulma
LeetCode 19 'Listenin Sonundan N'inci Düğümü Kaldırma': sondan n'inci düğümü tek geçişte bulun. Aralarında tam olarak n düğüm bulunan iki işaretçi kullanın. fast işaretçisini slow işaretçisinin n adım önüne ilerletin. Ardından fast son düğüme ulaşana kadar ikisini birlikte ilerletin. Bu noktada slow, sondan (n+1)'inci düğümdedir; yani kaldırılacak düğümün öncülüdür.
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]N'inci Düğümü Kaldırırken N+1 Adımın Nedeni
Temel incelik, sahte baş düğümden başlayarak hızlı işaretçiyi n değil, n+1 adım ilerletmektir. n+1 adımdan sonra hızlı işaretçi, her ikisi de sahte baş düğümden başlatılmışken, yavaş işaretçinin n+1 adım önündedir. Hızlı işaretçi boş değere ulaştığında, yavaş işaretçi boş değerin n+1 konum gerisindedir; bu da sıfırdan sayıldığında (uzunluk - n - 1) konumunda, yani hedefin öncülü olduğu anlamına gelir. Böylece slow.next = slow.next.next ifadesi sondan n'inci düğümü temiz biçimde silebilir.
# 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]')İki Bağlı Listenin Kesişimi
LeetCode 160 'İki Bağlı Listenin Kesişimi': iki listenin ilk kez kesiştiği düğümü bulun. O(1) alan kullanan yöntem şöyledir: her liste için birer tane olmak üzere iki işaretçiyi ilerletin. Bir işaretçi boş değere ulaştığında onu diğer listenin başına yönlendirin. En fazla A'nın uzunluğu + B'nin uzunluğu kadar adımdan sonra iki işaretçi de aynı toplam mesafeyi katetmiş olur ve kesişim düğümünde bulunmaları gerekir; kesişim yoksa ikisi de boş değerde olur.
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) # 8K Sıralı Listenin Birleştirilmesi (Böl ve Yönet)
LeetCode 23 'K Sıralı Listeyi Birleştirme': k sıralı liste verildiğinde bunları tek bir listede birleştirin. En uygun yaklaşım, böl ve yönet yöntemini kullanarak liste çiftlerini tekrar tekrar birleştirmek ve her turda liste sayısını yarıya indirmektir. Ortalama uzunluğu n olan k liste için bu işlem, sıralı birleştirmedeki O(n k²) yerine O(n k log k) zaman alır. Minimum yığın kullanan yaklaşım da O(n k log k) zaman alır.
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]Tek-Çift Bağlı Liste
LeetCode 328 'Tek-Çift Bağlı Liste': tüm tek indeksli düğüpleri, ardından çift indeksli düğümleri gruplayın (indeksler 1 tabanlıdır). Yaklaşım şöyledir: tek ve çift düğümler için iki ayrı zincir tutun ve işlem tamamlandığında bunları birbirine bağlayın. Listede tek bir geçiş yeterlidir; böylece zaman O(n), alan da O(1) olur. Bu, farklı adım aralıklarıyla iki işaretçiyi aynı anda ilerletmeye güzel bir örnektir.
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]Hepsini Bir Araya Getirme
Bu dersteki üç kalıp — sıralı listeleri birleştirme, orta noktadan bölme ve sondan n'inciyi bulma — ortak bir temayı paylaşır: ek bellek kullanmadan konumları izlemek için fazladan işaretçi değişkenleri kullanmak. Sahte baş düğüm, birleştirme ve silme işlemlerini basitleştirir; yavaş-hızlı işaretçi aralığı belirli bir göreli konumu sabitler; bir işaretçiyi önce ilerletmek istenen ayrımı oluşturur.
Bir mülakatta kod yazmaya başlamadan önce kullandığınız kalıbı belirtin: 'Tek geçişte sondan n'inci düğümü bulmak için iki işaretçili aralık tekniğini kullanacağım.' Bu, yapılandırılmış düşündüğünüzü gösterir.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayıp anlamadığınızı test edin.
Ders Özeti
Bu derste şunları öğrendiniz: iki sıralı listeyi birleştirmek, O(n+m) zamanda ve O(1) alanda sahte baş düğüm ile her adımda karşılaştırma kullanır, orta noktadan bölme, hızlı işaretçinin son geçerli çifte gelmesini sağlayan yavaş-hızlı işaretçileri kullanır ve sondan n'inciyi bulmak için hızlı işaretçi n+1 adım öne ilerletilir; böylece yavaş işaretçi öncüde konumlanır. Sırada yığınlar ve kuyruklar oluşturup bunları klasik mülakat problemlerinde kullanmak var.
Sıkça Sorulan Sorular
“Birleştirme, Bölme ve Sondan N’inciyi Bulma” dersi ücretsiz mi?
Evet — “Birleştirme, Bölme ve Sondan N’inciyi Bulma” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Birleştirme, Bölme ve Sondan N’inciyi Bulma” dersinde ne öğreneceğim?
İki sıralı bağlı listeyi O(n) sürede birleştirin, yavaş-hızlı işaretçilerle listeyi orta noktadan bölün ve sondan n’inci düğümü bulun. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.
“Birleştirme, Bölme ve Sondan N’inciyi Bulma” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Düğüm Sınıfı ve Liste Oluşturma
- Bağlı Listeyi Ters Çevirme
- Floyd Algoritmasıyla Döngü Algılama
- Birleştirme, Bölme ve Sondan N’inciyi Bulma