0Pricing
Coding Interview Prep · Ders

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 Coding 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, 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.

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.next

Adı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.next

Alt 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.next

K 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.next

Palindrom 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])))    # False

Yinelemeli 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.next

Listeyi 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 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.

“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. 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 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 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

  1. Düğüm Sınıfı ve Liste Oluşturma
  2. Bağlı Listeyi Ters Çevirme
  3. Floyd Algoritmasıyla Döngü Algılama
  4. Birleştirme, Bölme ve Sondan N’inciyi Bulma
← Coding Interview Prep Sayfasına Dön