Bağlı Listeyi Ters Çevirme
Tek yönlü bağlı listeyi üç işaretçinin yeniden bağlanmasıyla yinelemeli olarak ve özyinelemeli biçimde ters çevirin; her adımı tahta üzerindeki bir şemayı andıran çizimde izleyin.
Bağlı Listeyi Ters Çevirme, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 2. 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, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Liste Ters Çevirme Neden Önemlidir
Bağlantılı listeyi ters çevirmek, kodlama mülakatlarında en sık sorulan sorular arasındadır. Düğümlerin izini kaybetmeden işaretçileri hassas biçimde değiştirme becerinizi sınar. Çeşitleri hem bağımsız problemler olarak hem de palindrom algılama, listeyi yeniden sıralama ve k'lı grup ters çevirme gibi daha büyük algoritmaların alt adımları olarak karşınıza çıkar.
Yinelemeli yaklaşım üç işaretçi kullanır: prev, curr ve next_node. Özyinelemeli yaklaşım aynı mantığı çağrı yığını üzerinden gezinme olarak ifade eder. Her ikisi de O(n) zaman kullanır; yinelemeli yaklaşım ayrıca O(1) alan kullanır.
Üç İşaretçiyle Yinelemeli Ters Çevirme
Yinelemeli ters çevirmenin her adımında şunları yapın: listenin kalanını kaybetmemek için curr.next'i kaydedin, curr.next'i geriye doğru prev'e işaret edecek şekilde tersine çevirin, prev'i curr'ye ilerletin ve curr'yi kaydedilen sonraki düğüme ilerletin. curr None olduğunda döngü sona erer ve prev yeni head olur.
Yararlı bir hatırlatma: Kaydet, Tersine Çevir, İlerlet, İlerlet.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # Save
curr.next = prev # Flip
prev = curr # Advance prev
curr = next_node # Advance curr
return prev # new head
# Test
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list(nodes[0])
while head:
print(head.val, end=' ') # 5 4 3 2 1
head = head.nextAdım Adım İzleme
reverse_list işlevini 1 -> 2 -> 3 üzerinde izleyelim. Başlangıçta prev=None, curr=1. 1. adım: next=2 değerini kaydedin, 1.next=None bağlantısını tersine çevirin, prev=1, curr=2. 2. adım: next=3 değerini kaydedin, 2.next=1 bağlantısını tersine çevirin, prev=2, curr=3. 3. adım: next=None değerini kaydedin, 3.next=2 bağlantısını tersine çevirin, prev=3, curr=None. Döngü sona erer; 3 -> 2 -> 1 listesinin yeni başı olan prev=3 döndürülür.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_traced(head):
prev, curr = None, head
step = 0
while curr:
step += 1
next_node = curr.next
curr.next = prev
print(f'Step {step}: flipped {curr.val}.next -> {prev.val if prev else None}')
prev = curr
curr = next_node
return prev
nodes = [ListNode(i) for i in [1, 2, 3]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_traced(nodes[0])
print('New head:', head.val) # 3Özyinelemeli Tersine Çevirme
Özyinelemeli yaklaşım, reverse_list(head.next) çağrısının zaten tersine çevrilmiş sonekin yeni başını döndürdüğünü varsayar. Geriye yalnızca head ile head.next arasındaki işaretçiyi tersine çevirmek kalır: head.next.next = head ayarıyla eski ikinci düğümü eski ilk düğüme yönlendirin ve head.next = None ayarıyla eski ileri bağlantıyı kesin. Yeni baş düğüm temel durumdan yukarı doğru taşınır.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_rec(head):
# Base case: empty or single node
if not head or not head.next:
return head
new_head = reverse_list_rec(head.next) # reverse suffix
head.next.next = head # former second node points back
head.next = None # sever forward link
return new_head
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_rec(nodes[0])
while head:
print(head.val, end=' ') # 4 3 2 1
head = head.nextAlt Listeyi Tersine Çevirme (LeetCode 92)
LeetCode 92, 'Bağlı Listeyi Tersine Çevirme II', sol konumdan sağ konuma kadar olan alt listeyi (1 tabanlı indekslemeyle) tek geçişte tersine çevirmenizi ister. Buradaki püf nokta, alt listenin öncesindeki düğümü bulmak (bunun her zaman geçerli olması için sahte bir baş düğüm kullanın), üç işaretçili tersine çevirme işlemini tam olarak (right - left) adım boyunca gerçekleştirmek ve son olarak tersine çevrilen parçayı çevresindeki listeye yeniden bağlamaktır.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseBetween(head, left, right):
dummy = ListNode(0, head)
pre = dummy
# Advance pre to node just before position 'left'
for _ in range(left - 1):
pre = pre.next
curr = pre.next
for _ in range(right - left):
next_node = curr.next
curr.next = next_node.next
next_node.next = pre.next
pre.next = next_node
return dummy.next
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseBetween(nodes[0], 2, 4)
while head:
print(head.val, end=' ') # 1 4 3 2 5
head = head.nextK Grubundaki Düğümleri Tersine Çevirme (LeetCode 25)
LeetCode 25, 'Düğümleri k Grubunda Tersine Çevirme', art arda gelen her k düğümlük grubu tersine çevirir. Yaklaşım şöyledir: k düğüm kalıp kalmadığını kontrol edin; kalmadıysa bu düğümleri olduğu gibi bırakın. Sonraki k düğümü yinelemeli yöntemi kullanarak tersine çevirin, ardından listenin kalanını özyinelemeli olarak tersine çevirip birbirine bağlayın. Zaman karmaşıklığı O(n), özyinelemeli çağrı derinliği ise O(n/k) olduğundan değişmez.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseKGroup(head, k):
# Check if k nodes are available
curr, count = head, 0
while curr and count < k:
curr = curr.next
count += 1
if count < k:
return head # fewer than k nodes left, keep as-is
# Reverse k nodes
prev, curr = None, head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# head is now the tail of the reversed group
head.next = reverseKGroup(curr, k)
return prev
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseKGroup(nodes[0], 2)
while head:
print(head.val, end=' ') # 2 1 4 3 5
head = head.nextPalindrom Bağlı Liste
LeetCode 234, 'Palindrom Bağlı Liste': bir bağlı listenin O(n) zamanda ve O(1) bellek alanında palindrom olup olmadığını kontrol edin. Strateji: yavaş-hızlı işaretçilerle orta noktayı bulun, ikinci yarıyı yerinde tersine çevirin, iki yarıyı düğüm düğüm karşılaştırın ve ardından listeyi isteğe bağlı olarak eski hâline getirin. Bu işlem, orta nokta bulma ve tersine çevirme olmak üzere iki temel beceriyi bir araya getirir.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def isPalindrome(head):
# Find mid
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Compare
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
def build(arr):
d = ListNode(0)
c = d
for v in arr:
c.next = ListNode(v)
c = c.next
return d.next
print(isPalindrome(build([1,2,2,1]))) # True
print(isPalindrome(build([1,2,3]))) # FalseYinelemeli ve Özyinelemeli Yaklaşımların Karşılaştırması
Yinelemeli tersine çevirme O(1) bellek alanı kullanır ve genellikle tercih edilir. Özyinelemeli tersine çevirme, çağrı derinliği nedeniyle O(n) yığın alanı kullanır; bu da çok uzun listelerde yığın taşmasına yol açabilir (Python'un varsayılan sınırı yaklaşık 1000 özyineleme düzeyidir).
Bir mülakatta, bellek kısıtlarının farkında olduğunuzu göstermek için önce yinelemeli sürümü uygulayın; ardından liste uzunluğu sınırlıysa özyinelemeli sürümün daha temiz bir alternatif olduğundan söz edin.
import sys
print('Default recursion limit:', sys.getrecursionlimit())
# For a list of 10,000 nodes the recursive reversal would hit this limit
# Iterative reversal has no such constraint
# Increase if needed (use sparingly):
# sys.setrecursionlimit(20000)Tersine Çevirme İşleminde Yaygın Hatalar
Neredeyse tüm tersine çevirme hataları üç hatadan kaynaklanır. İlk olarak, üzerine yazmadan önce next değerini kaydetmemek: curr.next = prev, next_node kaydedilmediyse ileriye olan başvuruyu yok eder. İkinci olarak, prev değerini döndürmemek: döngünün sonunda curr None'dur, ancak prev yeni baş düğümdür. Üçüncüsü, yanlış özyinelemeli temel durum: not head.next unutulursa tek düğümlü liste işlenemez ve bir AttributeError oluşur.
# Minimal correct iterative reversal — annotated against common bugs
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # BUG if omitted: lose rest of list
curr.next = prev
prev = curr
curr = next_node
return prev # BUG if you return curr: it is None
nodes = [ListNode(i) for i in [1, 2, 3]]
nodes[0].next = nodes[1]
nodes[1].next = nodes[2]
h = reverse_list(nodes[0])
while h:
print(h.val, end=' ') # 3 2 1
h = h.nextListeyi Yeniden Sıralama (LeetCode 143)
LeetCode 143, 'Listeyi Yeniden Sıralama', L0 → L1 → L2 → ... → Ln listesini O(n) zamanda ve O(1) bellek alanında L0 → Ln → L1 → Ln-1 → L2 → Ln-2 biçimine dönüştürür. Çözüm üç adımı birleştirir: orta noktayı bulmak, ikinci yarıyı tersine çevirmek ve iki yarıyı dönüşümlü olarak birleştirmek. Tersine çevirme işleminde ustalaşmak, ilk bakışta karmaşık görünen bu problemi tanıdık araçların basit bir birleşimine dönüştürür.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reorderList(head):
if not head or not head.next:
return
# Find mid
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow.next
slow.next = None
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Interleave
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
reorderList(nodes[0])
h = nodes[0]
while h:
print(h.val, end=' ') # 1 4 2 3
h = h.nextÖzet: Tersine Çevirme Bir Yapı Taşıdır
Bağlı listeyi tersine çevirmek nadiren nihai hedeftir; bu işlem bir yapı taşıdır. Palindrom algılama, k grubu tersine çevirme, listeyi yeniden sıralama ve konumlar arasındaki bölümü tersine çevirme işlemlerinin tümü aynı üç işaretçili yinelemeli kalıba dayanır. Kalıp otomatikleştiğinde, zihinsel kapasitenizi daha üst düzeydeki problem yapısına odaklayabilirsiniz.
Tersine çevirme işlemini, iki dakikadan kısa sürede ezberden yazabilecek duruma gelene kadar mutlaka çalışın; bu işlem, neredeyse her bağlı liste mülakat turunda bir biçimde karşınıza çıkacaktır.
Hızlı Kontrol
Bu derste ele alınan Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını ne kadar anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: yinelemeli Kaydet-Tersine Çevir-İlerlet-İlerlet kalıbı, bir listeyi O(n) zamanda ve O(1) bellek alanında tersine çevirir, özyinelemeli yaklaşım sonekin zaten tersine çevrilmiş olduğunu varsayar ve yalnızca son bağlantıyı düzeltir ve tersine çevirme, palindrom algılama, listeyi yeniden sıralama ve k grubu tersine çevirme işlemlerinde temel bir alt adımdır. Sırada Floyd algoritmasıyla döngü algılamayı inceleyeceğiz.
Sıkça Sorulan Sorular
“Bağlı Listeyi Ters Çevirme” dersi ücretsiz mi?
Evet — “Bağlı Listeyi Ters Çevirme” 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 DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Bağlı Listeyi Ters Çevirme” dersinde ne öğreneceğim?
Tek yönlü bağlı listeyi üç işaretçinin yeniden bağlanmasıyla yinelemeli olarak ve özyinelemeli biçimde ters çevirin; her adımı tahta üzerindeki bir şemayı andıran çizimde izleyin. DSA 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.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA 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 2. dersidir.
“Bağlı Listeyi Ters Çevirme” 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 DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA 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