Zincir tersten de aynı mı
Görev tanımı
Problem
Rakamlardan oluşan tek yönlü bir bağlı listenin (linked list) head'i verildiğinde, değerler baştan sona ve sondan başa aynı okunuyorsa True döndür. Listede 1 ile 100.000 arasında düğüm var. O(n) zaman ve O(1) ek bellek hedefle; bu, değerleri bir Python listesine kopyalamayı dışarıda bırakır. İşin bitince listeyi orijinal şekliyle bırak.
Örnekler
Input: 1 -> 2 -> 2 -> 1
Output: True
Input: 1 -> 2
Output: False
Input: 7
Output: True
Neden: edge case: tek düğüm bir palindromdur
İpuçları
0 / 3
Bir dizide ilk değeri sonuncusuyla karşılaştırmak kolay, ama tek yönlü bir bağlı liste geriye doğru gidemez. Arka yarı ters yönü gösterseydi ne olurdu?
Yavaş bir pointer'ı birer, hızlı bir pointer'ı ikişer adım ilerlet. Hızlı olan bitince yavaş olan arka yarının başındadır.
Arka yarıyı yerinde ters çevir, ön yarıyla yan yana dolaşarak değerleri karşılaştır, sonra listeyi geri getirmek için onu yeniden ters çevir.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- the list has between 1 and 10⁵ nodes
- each node holds a digit
Çözüm
Bir palindrom kontrolü baştan i. değeri sondan i. değerle karşılaştırır; tek engel tek yönlü bir bağlı listenin arkasının tersten dolaşılamaması. Hızlı ve yavaş pointer'lar (fast & slow pointers) ortayı tek geçişte bulur: hızlı pointer bitince yavaş olan arka yarının ilk düğümünde (tek uzunlukta ortadaki düğümün kendisinde) durur. Listeyi oradan ters çevirmek arka yarıyı son düğümden içe doğru okunabilir yapar, böylece iki pointer onu ön yarıyla karşılaştırabilir. Karşılaştırma ters çevrilmiş yarı bitince durur; bu, yalnız kalan ortadaki düğümü de yok sayar. O yarıyı ikinci kez ters çevirmek her bağlantıyı yerine koyar. Zaman O(n), ek 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 reverse(node):
prev = None
while node:
node.next, prev, node = prev, node, node.next
return prev
def is_palindrome(head):
slow = fast = head
while fast and fast.next: # slow ends at the back half
slow, fast = slow.next, fast.next.next
tail = reverse(slow)
left, right, same = head, tail, True
while right:
if left.val != right.val:
same = False
break
left, right = left.next, right.next
reverse(tail) # restore the original links
return same
print(is_palindrome(build([1, 2, 2, 1]))) # -> True
print(is_palindrome(build([1, 2]))) # -> False
print(is_palindrome(build([7]))) # -> True
chain = build([1, 2, 3, 2, 1])
print(is_palindrome(chain), dump(chain)) # -> True [1, 2, 3, 2, 1]Kodda değil de fikirde mi takıldın? Hızlı ve yavaş pointer bunu anlatıyor.