Leetcode 206 Reverse Linked List

Soru

Given the head of a singly linked list, reverse the list, and return the reversed list.

Örnek 1

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Örnek 2

Input: head = [1,2]
Output: [2,1]

Örnek 3

Input: head = []
Output: []

Çözüm

• Verilen tek yönlü bir bağlı listenin (linked list) elemanlarını ters çevirmenizi ister. Bu soru, verilen bir tek yönlü bağlı listenin düğümlerini ters sırayla düzenlemenizi ve ters çevrilen listenin başını (head) döndürmenizi gerektirir.
• Girdi: Tek yönlü bir bağlı listenin baş düğümü (head).
• Çıktı: Aynı liste, ancak düğümler ters sıralı.
• Bu problem genellikle yinelemeli (iterative) veya özyinelemeli (recursive) yöntemlerle çözülür. Her iki yöntem de liste düğümlerinin işaretçilerini (pointers) tersine çevirerek çalışır.
• Çalışma Mekanizması: Her iki çözüm de bağlı listenin düğümlerinin next işaretçilerini ters çevirerek listenin tersine çevrilmesini sağlar. Yinelemeli çözümde bu işlem bir döngü içinde, özyinelemeli çözümde ise özyinelemeli fonksiyon çağrılarıyla gerçekleştirilir.

Code

• Yinelemeli Çözüm: Yinelemeli çözümde, mevcut düğümü işlerken bir önceki düğümü izlemek için bir değişken kullanılır. Bu değişken, düğüm bağlantılarını ters çevirmek için gereklidir.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head):
        prev = None
        current = head
        while current:
            next_node = current.next  # Sonraki düğümü sakla
            current.next = prev  # Mevcut düğümü ters çevir
            prev = current  # Önceki düğümü güncelle
            current = next_node  # İlerle
        return prev  # Yeni baş düğümü

• Özyinelemeli Çözüm: Özyinelemeli çözümde, fonksiyon kendisini liste sonuna kadar çağırır ve geri dönüş yolunda düğüm işaretçilerini tersine çevirir.

class Solution:
    def reverseList(self, head):
        if not head or not head.next:
            return head  # Base case: Liste boş veya tek düğümlü
        p = self.reverseList(head.next)  # Liste sonuna kadar git
        head.next.next = head  # Ters çevirme işlemi
        head.next = None  # Eski baş düğümünü son düğüm yap
        return p  # Yeni baş düğümü

Complexity

• Time complexity (Zaman Karmaşıklığı): Her iki çözüm için de O(n), burada n düğüm sayısıdır.
• Space complexity (Alan Karmaşıklığı): Yinelemeli çözüm için O(1), çünkü sadece sabit miktarda ekstra alan kullanılır. Özyinelemeli çözüm için O(n), özyinelemeli çağrılar için çağrı yığınında n adet kayıt tutulur.