Leetcode 143 Reorder List

Soru

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Örnek 1

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

Örnek 2

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

Çözüm

• Verilen bir tek yönlü bağlı listenin düğümlerini özel bir sırayla yeniden düzenlemenizi ister. Bu problemde, listenin ilk elemanını son eleman, ikinci elemanı sondan ikinci eleman ve bu şekilde devam edecek biçimde yeniden düzenlenmesi gerekiyor.
• Girdi: Tek yönlü bir bağlı listenin baş düğümü (head).
• Çıktı: Düğümler yukarıda açıklanan sırayla yeniden düzenlenmiş liste. Fonksiyon dönüş değeri olmadan listeyi yerinde (in-place) değiştirmelidir.
• Çalışma Mekanizması:
• Listeyi Ortadan Bölmek: Hızlı ve yavaş işaretçiler kullanılarak liste ortadan ikiye bölünür. Hızlı işaretçi her adımda iki düğüm, yavaş işaretçi bir düğüm ilerler.
• Listeyi Ters Çevirmek: İkinci yarının başlangıcından itibaren liste sonuna kadar düğümler ters çevrilir.
• Listeleri Birleştirmek: İlk liste ile tersine çevrilmiş ikinci liste, özellikle belirtilen sırayla birleştirilir. Bu işlem sırasında, birinci listeden bir düğüm, ikinci listeden bir düğüm şeklinde ilerlenir.

Code

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

class Solution:
    def reorderList(self, head):
        if not head:
            return
        
        # Adım 1: Orta noktayı bul
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # Adım 2: İkinci yarısını ters çevir
        prev, curr = None, slow
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        
        # Adım 3: İki listeyi birleştir
        first, second = head, prev
        while second.next:
            temp1, temp2 = first.next, second.next
            first.next = second
            second.next = temp1
            first, second = temp1, temp2

Complexity

• Time complexity (Zaman Karmaşıklığı): O(n), burada n bağlı listenin düğüm sayısıdır. Listenin ortasını bulmak, ikinci yarısını tersine çevirmek ve listeleri birleştirmek lineer zaman alır.
• Space complexity (Alan Karmaşıklığı): O(1), çünkü ek alan kullanılmaz; tüm değişiklikler mevcut liste üzerinde yerinde gerçekleştirilir.