Leetcode 25 Reverse Nodes in k-Group

Soru

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Follow-up: Can you solve the problem in O(1) extra memory space?

Örnek 1

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

Örnek 2

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

Çözüm

• “25. Reverse Nodes in k-Group” sorusu, verilen bir bağlı listeyi her k düğümde gruplayarak ters çevirme işlemini gerçekleştirmenizi ister. Bu problemde, bağlı liste boyunca ilerlerken her k düğüm tersine çevrilmeli ve k’ya tam bölünmeyen son grup olduğu gibi bırakılmalıdır.
• Girdi: Tek yönlü bir bağlı listenin baş düğümü (head) ve bir tam sayı k.
• Çıktı: Bağlı listenin her k düğümünde tersine çevrilmiş hali.
• Bu problemi çözmek için, liste boyunca ilerleyip her k düğüm için ters çevirme işlemi yapabiliriz. Bunun için iki aşamalı bir yaklaşım kullanılır: ilk olarak, verilen k boyutunda bir grubun tamamının tersine çevrilebilir olup olmadığını kontrol etmek, ardından bu grubu tersine çevirmek.
• Çalışma Mekanizması:
• Grubun Ters Çevrilebilirliğini Kontrol Et: Her grup için, grup boyunca ilerleyip k düğüme ulaşılıp ulaşılamayacağını kontrol eder.
• Grubu Ters Çevirme: Grup ters çevrilebilir ise, o grubu yerinde ters çevirir.
• Listeyi Yeniden Bağla: Ters çevrilen grubun başını ve sonunu, ana listeye bağlar.
• Sonraki Gruba Geçiş: İşlem, liste sonuna kadar veya bir grup k düğümden kısa olduğunda durdurulur.

Code

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

class Solution:
    def reverseKGroup(self, head, k):
        # Grup ters çevrilebilir mi kontrol et
        def canReverse(start, k):
            count = 0
            while start and count < k:
                start = start.next
                count += 1
            return count == k
        
        # Verilen başlangıçtan itibaren k düğümü ters çevir
        def reverse(start, k):
            prev, curr = None, start
            for _ in range(k):
                next_temp = curr.next
                curr.next = prev
                prev = curr
                curr = next_temp
            return prev
        
        dummy = ListNode(0, head)
        prev_group_end = dummy
        
        while canReverse(prev_group_end.next, k):
            kth = prev_group_end
            # k'inci düğümü bul
            for _ in range(k):
                kth = kth.next
            group_next = kth.next
            # k düğümü ters çevir
            new_start = reverse(prev_group_end.next, k)
            # Ters çevrilen grubu listeyle birleştir
            kth = prev_group_end.next
            prev_group_end.next = new_start
            kth.next = group_next
            prev_group_end = kth
            
        return dummy.next

Complexity

• Time complexity (Zaman Karmaşıklığı): O(n), burada n düğüm sayısıdır. Her düğüm birkaç kez işlenir (kontrol ve ters çevirme işlemleri).
• Space complexity (Alan Karmaşıklığı): O(1), çünkü ek alan kullanılmaz; tüm işlemler mevcut liste üzerinde gerçekleştirilir.