Takip et

Sıralı Listede Tekrar Eden Elemanları Kaldırma (II)

Sıralı Listede Tekrar Eden Elemanları Kaldırma (II)

Merhaba, ben Fatih Soysal. Bugün, “Sıralı Listede Tekrar Eden Elemanları Kaldırma II” problemini detaylı bir şekilde ele alacağız. Bu problem, verilen sıralı bir bağlı listedeki ardışık tekrar eden elemanları kaldırmayı gerektirir. Örneğin, 1->2->3->3->4->4->4->5 listesinde 3 ve 4’ün tekrar eden tüm örnekleri kaldırıldığında 1->2->5 listesi elde edilir. Bu problemi çözmek için çeşitli yaklaşımlar mevcuttur. Ancak en etkili çözüm, iteratif bir yaklaşım kullanmaktır.

Öncelikle, problemimizi daha iyi anlamak için bir örnek inceleyelim. Diyelim ki elimizde şu bağlı liste var: 1 → 2 → 3 → 3 → 4 → 4 → 5. Amacımız, tekrar eden elemanları kaldırarak 1 → 2 → 5 listesini elde etmek. Bu işlemi nasıl gerçekleştirebileceğimize bakalım.

Iteratif Yaklaşım

Bu problem için en verimli yöntem, iteratif bir yaklaşım kullanmaktır. Bu yaklaşımda, liste üzerinde tek bir geçiş yaparak tekrar eden elemanları tespit edip kaldıracağız. İşte bu yaklaşımın Python’daki kod örneği:


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

def deleteDuplicates(head):
    if not head:
        return head

    dummy = ListNode(0, head)  # Dummy node ekliyoruz
    prev = dummy

    while head:
        if head.next and head.val == head.next.val:  # Tekrar eden eleman varsa
            while head.next and head.val == head.next.val:  # Tüm tekrar edenleri buluyoruz
                head = head.next
            prev.next = head.next  # Tekrar edenleri atlıyoruz
            head = head.next # Bir sonraki elemana geçiyoruz

        else:
            prev = head
            head = head.next

    return dummy.next

Kodumuzda öncelikle bir dummy node ekliyoruz. Bu node, listenin başına eklenerek başlangıç durumunda özel bir durumla karşılaşmamızı engeller. Daha sonra while döngüsü ile listeyi geziyor ve ardışık tekrar eden elemanları tespit ederek, prev.next = head.next satırı ile bu elemanları listeden çıkarıyoruz. Sonuç olarak, tekrar eden elemanları kaldırılmış bir liste elde ediyoruz. Burada dikkat edilmesi gereken nokta, while döngüsünün tüm tekrar eden elemanları atlamasıdır.

Karmaşıklık Analizi

Algoritmamızın zaman karmaşıklığı O(n) ‘dir, burada n listenin uzunluğudur. Çünkü liste üzerinde sadece tek bir geçiş yapıyoruz. Bellek karmaşıklığı ise O(1)’dir çünkü ek bir veri yapısı kullanmıyoruz. Yani algoritmamız hem zaman hem de bellek açısından oldukça verimlidir.

Alternatif Yaklaşımlar

Bu problemi çözmek için rekursif yaklaşımlar da kullanılabilir, ancak iteratif yaklaşım genellikle daha verimli ve okunabilirdir. Rekursif çözümler daha karmaşık olabilir ve büyük listelerde yığın taşması (stack overflow) sorununa yol açabilir.

Umarım bu makale size “Sıralı Listede Tekrar Eden Elemanları Kaldırma II” problemini anlamada yardımcı olmuştur. Daha fazla bilgi için bu kaynağa bakabilirsiniz. Ayrıca, daha fazla yazılım geliştirme içeriği için web sitemi ziyaret edebilirsiniz.

#Etiketler: Sıralı Liste, Bağlı Liste, Tekrar Eden Elemanlar, Veri Yapıları, Algoritmalar, Python, Kodlama, Programlama, Linked List, Duplicate Removal, Iterative Approach, Data Structures, Algorithms

Yorumlar
İçeriği beğendiniz mi? Bir tartışma başlatın veya görüşlerinizi paylaşın.
Yorum Yaz

Bir yanıt yazın

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

E-posta Bülteni
Yazılım Topluluğuna Katılın
En son güncellemeleri, yaratıcı ipuçlarını ve özel kaynakları doğrudan e-posta kutunuza alın. Tasarım ve inovasyonun geleceğini birlikte keşfedelim.