Leetcode 019 Remove Nth Node From End of List

Soru

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Örnek 1

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

Örnek 2

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

Örnek 3

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

Çözüm

• Tek yönlü bir bağlı listeden sonundan n’inci düğümü silmenizi ister. Bu problem, verilen bir bağlı listenin sonundan n’inci düğümün kaldırılmasını ve listenin güncellenmiş baş düğümünün döndürülmesini gerektirir.
• Girdi: Tek yönlü bir bağlı listenin baş düğümü (head) ve bir tam sayı n.
• Çıktı: Sonundan n’inci düğüm çıkarılmış bağlı liste.
• Bu problemi çözmek için sıkça kullanılan bir yöntem, iki işaretçi tekniği kullanmaktır. İki işaretçi (pointer) arasında sabit bir aralık (n düğüm) korunarak, birinci işaretçi listenin sonuna ulaştığında, ikinci işaretçi silinecek düğümün bir öncesinde olacak şekilde ayarlanır. Bu teknik, liste boyunca yalnızca bir kez geçilmesini sağlar, bu da işlemi verimli kılar.
• Çalışma Mekanizması:
• Dummy Düğüm Kullanımı: Silinecek düğüm baş düğüm olduğunda, baş düğümün kolayca güncellenebilmesi için bir dummy düğüm kullanılır.
• İki İşaretçi Arasındaki Mesafe: İlk işaretçi, ikinci işaretçiden n+1 düğüm ileri taşınır. Bu, ikinci işaretçinin, silinecek düğümün bir öncesinde kalmasını sağlar.
• İşaretçilerin İlerletilmesi: İlk işaretçi listenin sonuna ulaşana kadar her iki işaretçi de birer düğüm ileri taşınır.
• Düğümün Çıkarılması: İkinci işaretçi, silinecek düğümün bir öncesindedir. Bu düğümün next işaretçisi, silinecek düğümü atlayacak şekilde güncellenir.
• Sonuç: Dummy’nin next özelliği, güncellenmiş listeyi gösterir ve bu değer döndürülür.

Code

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

class Solution:
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)  # Dummy düğüm, edge case'leri kolaylaştırır
        dummy.next = head
        first = dummy
        second = dummy

        # İlk işaretçiyi n+1 düğüm ileri taşı
        for i in range(n+1):
            first = first.next

        # İlk işaretçi sona ulaşana kadar ilerle
        while first is not None:
            first = first.next
            second = second.next

        # n'inci düğümü çıkar
        second.next = second.next.next

        return dummy.next

Complexity

• Time complexity (Zaman Karmaşıklığı): O(L), burada L bağlı listenin uzunluğudur. Liste baştan sona bir kez taranır.
• Space complexity (Alan Karmaşıklığı): O(1), çünkü sabit miktarda ekstra alan kullanılır; algoritma yerinde çalışır.