Değeri tutan düğümleri sil
Görev tanımı
Problem
Tek yönlü bir bağlı listenin (linked list) head'i ve bir hedef değer verildiğinde, o değeri tutan her düğümü sil ve kalanın head'ini döndür. Düğümler yeni bir listeye kopyalanmaz, bağlantıları koparılır; hayatta kalan düğümler orijinal sıralarını korur. Sonuç boş olabilir.
Örnekler
Input: head = 1 -> 2 -> 6 -> 3 -> 6, target = 6
Output: 1 -> 2 -> 3
Input: head = 7 -> 7 -> 7, target = 7
Output: empty
Neden: edge case: her düğüm eşleşiyor ve liste boşalıyor
Input: head = empty, target = 1
Output: empty
Neden: edge case: silinecek bir şey yok
İpuçları
0 / 3
Bir düğümü silmek onu gösteren şeyi değiştirmek demektir; yani üzerinde durduğun düğüm hiçbir zaman çıkarabileceğin düğüm değildir.
Adayın önündeki düğümde dur ve onun ardılını incele. Head'in öncülü yok; kendine bir tane uydurmazsan kendi dalını gerektirecek tek durum bu.
Her gerçek düğümün bir öncülü olsun diye head'in önüne atılacak bir düğüm koy. Sonraki düğümü inceleyen bir pointer'la dolaş: eşleşiyorsa bağlantısını kopar ve yerinde kal, çünkü yeni ardılın da incelenmesi gerekir; yalnız eşleşmiyorsa ileri adım at.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Çözüm
Head'den önce konan atılacak bir düğüm her gerçek düğüme bir öncül verir; böylece ilk düğümü silmek diğerlerini silmekle tamamen aynı yeniden bağlamayı kullanır. Dolaşan pointer kendisini değil ardılını inceler ve bir bağlantı koparmadan sonra bilerek yerinde kalır, çünkü o konuma kayan düğüm henüz incelenmemiştir. Bağlantı koparmadan sonra ilerlemek buradaki klasik hatadır, çünkü art arda gelen eşleşmeleri atlar. Zaman O(n), 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 remove_value(head, target):
dummy = Node(0, head) # lets head removal use the same relink
node = dummy
while node.next:
if node.next.val == target:
node.next = node.next.next # unhook, and do not move on
else:
node = node.next
return dummy.next
print(dump(remove_value(build([1, 2, 6, 3, 6]), 6))) # -> [1, 2, 3]
print(dump(remove_value(build([7, 7, 7]), 7))) # -> []
print(dump(remove_value(build([]), 1))) # -> []Kodda değil de fikirde mi takıldın? Ekleme ve silme bunu anlatıyor.