LeetCode #234 Palindrome Linked List: หา mid แล้วกลับครึ่งหลังเทียบ

Palindrome Linked List ถามว่าค่าในลิงก์ลิสต์อ่านกลับแล้วยังเท่าเดิมไหมครับ

วิธี 1: คัดลอกเป็นอาร์เรย์

ง่ายสุด O(n) พื้นที่ — ดีตอนดีบัก

วิธี 2: slow/fast หา mid + reverse ครึ่งหลัง

พื้นที่ O(1) เทียบทีละโหนด — คำตอบมาตรฐานสัมภาษณ์

วิธี 3: recursion สแต็กโดยนัย

สวยแต่กินสแต็ก O(n) — ระวังลิสต์ยาว

from __future__ import annotations
from dataclasses import dataclass
import unittest

@dataclass
class Node:
    val: int
    next: Node | None = None

def is_palindrome(head: Node | None) -> bool:
    if head is None or head.next is None:
        return True
    slow = fast = head
    while fast and fast.next:
        slow = slow.next  # type: ignore[assignment]
        fast = fast.next.next
    prev = None
    cur = slow
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    left, right = head, prev
    while right:
        if left is None or left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

def build(vals: list[int]) -> Node | None:
    dummy = Node(0)
    cur = dummy
    for v in vals:
        cur.next = Node(v)
        cur = cur.next
    return dummy.next

class PalindromeTests(unittest.TestCase):
    def test_true(self):
        self.assertTrue(is_palindrome(build([1, 2, 2, 1])))
    def test_false(self):
        self.assertFalse(is_palindrome(build([1, 2])))

if __name__ == "__main__":
    unittest.main()

ถ้าโจทย์ห้ามแก้ลิสต์ ให้ reverse กลับหลังเทียบ หรือใช้สำเนา

Recap

• ฝึก slow/fast จนชี้ mid ถูกทั้งคู่/คี่
• เขียน reverse ลิงก์ลิสต์ให้คล่องก่อน
• เทสต์ [1], [1,2,1], [1,2,2,1]