Palindrome Linked List - leetode 234

thoughts

• 判斷一個單向鏈結串列是否為迴文（palindrome）。

• Ex.

  • Input: 1 -> 2 -> 2 -> 1
    • Output: true
  • Input: 1 -> 2
    • Output: false

• 方法 1：將鏈表轉成陣列 (Brute Force)

• 遍歷鏈表，把所有值存進 List。

• 用雙指針從頭尾比較。

• 時間複雜度：O(n)

• 空間複雜度：O(n)

• 簡單，但佔額外空間，不是最佳解

• 方法 2：快慢指針 + 反轉後半鏈表, 常見解法

  • 步驟：
    1. 用快慢指針 (fast, slow) 找到中點：
    • fast 每次走兩步，slow 每次走一步。
    • 當 fast 到底時，slow 就在中點。
    2. 反轉 slow 之後的鏈表：
    • 將後半部分鏈表反轉。
    3. 從頭(head) 與 後半反轉部分 同步比較：
    • 逐一比對值是否相同。
    • 若有不等，回傳 false。
    4. (可選) 後半部分再反轉回來，恢復原鏈表。

• 時間複雜度：O(n)

• 空間複雜度：O(1)

• 方法 3：遞迴

• 利用遞迴「向內推進」並比較對稱節點。

  • 需要一個 global pointer 指向頭部，遞迴深入到底後回來比較。
  • 但會用到遞迴 stack，空間不是 O(1)。

Kotlin

class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        if (head?.next == null) return true
        
        // 1. 找到中點
        var slow = head
        var fast = head
        while (fast?.next != null && fast.next?.next != null) {
            slow = slow?.next
            fast = fast.next?.next
        }

        // 2. 反轉後半部分
        var secondHalf = reverseList(slow?.next)

        // 3. 比對前後半部分
        var p1 = head
        var p2 = secondHalf
        while (p2 != null) {
            if (p1?.`val` != p2.`val`) return false
            p1 = p1?.next
            p2 = p2.next
        }
        return true
    }

    private fun reverseList(head: ListNode?): ListNode? {
        var prev: ListNode? = null
        var curr = head
        while (curr != null) {
            val nextNode = curr.next
            curr.next = prev
            prev = curr
            curr = nextNode
        }
        return prev
    }
}

Follow-up

• 如何就地檢查而不使用額外空間？
  • 用方法 2，只需要 O(1) 空間。
• 如何處理雙向鏈表？
  • 可以直接用頭尾指針往中間比較。
• 如何在比較後恢復鏈表結構？
  • 再次反轉後半鏈表，接回去。
• 如果鏈表非常大，如何在流式（streaming）情境下檢查？
  • 可以結合 "快慢指針 + 滾動 hash" (Rabin-Karp)，但這可能超出面試範圍。
• 能否做到 O(1) 空間？（快慢指針 + 反轉後半）
• 如果需要保持原鏈表結構，該怎麼辦？（在檢查後再反轉一次後半部分）
• 是否可以在一次遍歷 中完成？（較難，需要邊走邊反轉）