Sıralı zincirleri birleştir
Görev tanımı
Problem
Tek yönlü iki bağlı listenin (linked list) her biri zaten azalmayan sırada sıralı. Yeni düğümler oluşturmak yerine mevcut düğümleri yeniden bağlayarak onları tek bir sıralı listede birleştir. Birleşmiş listenin head'ini (baş düğüm) döndür; iki girdi de boşsa liste de boştur.
Örnekler
Input: a = 1 -> 4 -> 6, b = 2 -> 3
Output: 1 -> 2 -> 3 -> 4 -> 6
Input: a = empty, b = 7
Output: 7
Neden: edge case: döngü başlamadan bir taraf tükeniyor
Input: a = empty, b = empty
Output: empty
Neden: edge case: birleştirilecek bir şey yok
İpuçları
0 / 3
Her an sıradaki olabilecek yalnız iki aday var: her zincirin o anki önü. İkisinden biri tüketilene kadar iki zincirin geri kalanı önemsiz.
Bir listeyi önden büyütmek zahmetli, bu yüzden sonucun son düğümüne bir pointer tut ve her zaman onun arkasına ekle. Atılacak bir başlangıç düğümü ilk eklemenin özel durumunu ortadan kaldırır.
İki ön düğümü tekrar tekrar karşılaştır, küçük olanı ayır ve sonucun tail'ine as. Bir zincir boşalınca kalan zincirin tamamını tek adımda bağla, çünkü o zaten sıralı.
- Hedef zaman
- O(n + m)
- Hedef alan
- O(1)
Kısıtlar
- both lists are sorted in non-decreasing order
- either list may be empty
Çözüm
İki zincir önden öne tüketilir; her seferinde küçük head alınır ve sonucun tail'ine (son düğüm) eklenir. Bir dummy başlangıç düğümü, ilk eklemenin özel bir işleme gerek duymaması demektir; gerçek head de basitçe ondan sonraki düğümdür. Bir zincir tükenince diğeri zaten sıralıdır, bu yüzden kalan kısım düğüm düğüm değil tek hamlede bağlanır. Yalnız pointer'lar değiştiği için zaman O(n + m), alan O(1).
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return Node(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def merge_sorted(a, b):
dummy = tail = Node(0) # starter node removes the empty-result case
while a and b:
if a.val <= b.val: tail.next, a = a, a.next
else: tail.next, b = b, b.next
tail = tail.next # the attached node is the new tail
tail.next = a or b # the leftover chain is already sorted
return dummy.next
print(dump(merge_sorted(build([1, 4, 6]), build([2, 3])))) # -> [1, 2, 3, 4, 6]
print(dump(merge_sorted(build([]), build([7])))) # -> [7]
print(dump(merge_sorted(build([]), build([])))) # -> []Kodda değil de fikirde mi takıldın? İki sıralı listeyi birleştirme bunu anlatıyor.