Problem surada.
Cozum
Bu problemi O(n) space ile cozmek trivial o yuzden direk olarak follow-up ile baslayalim ve O(1) space ve O(n) time ile nasil cozeriz bunu dusunelim.
Eger ileri ve geri olarak lined list uzerinde gezinebilse idik, ortasindan baslyarak yanlara dogru gider ve esitlik bozuluyorsa palindrome olmadigina karar verebilirdik. Peki geriye dogru gidemiyor ise, linkedlistin ilk yarisini ters cervirsek ve karsilastirmayi birincisi sifirdan ikincisi de linkedlistin tam ortasindan baslayacak sekilde iki pointer ile yapsak? Su sekilde:
1, 2, 2, 1 seklinde giden linked listi inceleyeim. Ilk yarisini ters cevirir isek, sonuca 2,1,2,1 seklinde bir hale gelir. Bu sekilde iken, i ve j olmak uzere iki pointer ile karsilastirma yapmak mumkun. Birincisi sifirdan ikincisi de ll'nin ortasindan baslayacak ve her adimda ikisini de 1 artiracagiz. Esitlik bozulursa False dondurecegiz.
O zaman ilk etapta linkedlistin uzunlugunu bulmamiz gerekiyor ki, ortsina kadar olan node'lari ters cevirebilelim ve de karsilastirmayi ortadan baslatabilelim.
def isPalindrome(self, head: ListNode) -> bool:
# gayet acik bir sekilde, linked list bitene kadar ilerliyoruz
# ve kac node oldugunu tutuyoruz
def length(head):
ret = 0
cur = head
while cur:
ret += 1
cur = cur.next
return ret
# orta noktasini bulalim
ll = length(head)
mid = ll // 2
if ll % 2 == 1:
# eger tek sayida node var ise
# orta noktasi kayacaktir soyle: 1, 2, 1 icin 1,2 ve 1 seklinde ayirmak istiyoruz.
# cunku ilk yarisini ters cevirdigimizde, ilk karsilastirma baslangic noktasi solda
# kalmasi gerekiyor
# bu islem aslinda math.ceil(linked_list_length / 2) seklinde de yapilabilirdi
mid += 1
# simdi orta noktaya kadar olan kismi dolasip
# ters ceviriyoruz
while mid > 0:
# bir nevi swap yaptgimiz icin next isimli ucuncu bir tmp degisken kullaniyoruz
next = cur.next
cur.next = prev
cur = next
prev = cur
# bu noktada eger cift sayida node var ise, 1,2,2,1 inputu icin sonuc: 2,1,2,1 gayet guzel
# ama tek sayida node var ise, 1,2,1 icin 2,1,1 seklinde. ve prev degiskeni 2 olarak kalmis durumda.
# bu yuzden prev'i bir tik ileri otelememiz gerekiyor
if ll % 2 == 1:
prev = prev.next
# simdi karsilastirma indisleri haizr, tek yapmamiz gereken sona kadar gidip
# degerleri karsilastirmak
while cur:
if cur.val != prev.val:
return False
cur = cur.next
prev = prev.next
# bu noktaya kadar geldiysek, elimizde bir palindrome var demektir
return True
Analiz
Ilk mantigi oturtmak ve daha sonra edge case'leri oturttuktan sonra straightforward bir problemdi. Ilk etapta list uzunlugunu hesapladik, O(n) time compl. Daha sonra yarisina kadar olan kismi reverse ettik ama kaldigimiz yerden de karsilastirma yapmaya devam ettik. Demek ki bir tam tur traverse var ve tekrar O(n) time compl. sahip bir islem. Programda hic ekstra hafiza kullanmadik, O(1) space compl. ile bu problemi burada noktaliyoruz.
Bir sonraki problemde gorusmek uzere. Stay hungry, stay foolish, stay healthy, stay sane :)
Yorumlar
Yorum Gönder