234. Palindrome Linked List

Easy

Description

給定一個單向鏈結串列的頭節點 head，判斷該鏈結串列是否為回文（palindrome）。

Example:

Input: head = [1,2,2,1] Output: true

Intuition#

核心思路：找到中點後反轉後半段，再逐一比對前半段與反轉後的後半段。

回文的特性是前後對稱，但單向鏈結串列只能往前走
方法一：用 Stack 或陣列存所有值，再雙向比對
方法二：快慢指針找中點 + 反轉後半段，O(1) 空間

Approaches#

1: Stack#

概念: 將所有節點值壓入 Stack，再從頭遍歷同時從 Stack 彈出比對
時間複雜度: O(n)
空間複雜度: O(n) - Stack 儲存所有節點值

class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        val stack = ArrayDeque<Int>()
        var curr = head
        while (curr != null) {
            stack.addLast(curr.`val`)
            curr = curr.next
        }
        curr = head
        while (curr != null) {
            if (curr.`val` != stack.removeLast()) return false
            curr = curr.next
        }
        return true
    }
}

⭐2: Fast-Slow Pointer + Reverse#

概念: 快慢指針找中點，反轉後半段鏈結串列，再逐一比對
時間複雜度: O(n)
空間複雜度: O(1) - 只用指針變數

class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        // 快慢指針找中點
        var slow = head
        var fast = head
        while (fast?.next != null) {
            slow = slow?.next
            fast = fast.next?.next
        }

        // 反轉後半段
        var prev: ListNode? = null
        var curr = slow
        while (curr != null) {
            val next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        }

        // 比對前半段與反轉後的後半段
        var left = head
        var right = prev
        while (right != null) {
            if (left?.`val` != right.`val`) return false
            left = left.next
            right = right.next
        }
        return true
    }
}

面試時可能會被問到是否需要還原鏈結串列。若需要，在比對完成後再反轉一次後半段即可。

🔑 Takeaways#

Pattern: 快慢指針找中點 + 鏈結串列反轉，是鏈結串列回文判斷的經典組合
關鍵技巧: 快慢指針停下時，slow 剛好在中間（奇數長度）或後半段起點（偶數長度），可以直接從 slow 開始反轉