前言

嘿嘿～今天我們要來解一道經典的鏈結串列題目——Palindrome Linked List（迴文鏈結串列）！
這題是 Easy 難度，但要解得漂亮可沒這麼簡單。

題目要我們判斷一個單向鏈結串列是否是迴文，說白了就是看它的值從前往後、從後往前是不是一樣，像讀到「1221」或「2332」這樣子，就像小時候玩的文字遊戲。
話不多說，我們直接來看看吧！

英文題目

Palindrome Linked List

Given the head of a singly linked list, return true if it is a 

palindrome

 or false otherwise.

Example 1:

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

Example 2:

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

題目描述：

給定一個單向鏈結串列的頭節點 head，如果該鏈結串列是迴文，返回 true；否則，返回 false。
請判斷該鏈結串列的值是否從前往後、從後往前讀都是一樣的，也就是是否為迴文結構。

範例 1：

輸入： head = [1,2,2,1]

輸出： true

範例 2：

輸入： head = [1,2]

輸出： false

實作

這道題的難點在於我們需要「原地處理」鏈結串列，無法直接新建陣列來反轉對比。因此，我們可以採用快慢指針配合反轉的技巧來判斷：

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

function isPalindrome(head: ListNode | null): boolean {
    if (!head || !head.next) return true;

    let slow = head;
    let fast = head;
    let prev: ListNode | null = null;

    // 用快慢指針找到鏈結串列的中點
    while (fast && fast.next) {
        fast = fast.next.next;
        // 反轉前半部分鏈結串列
        const next = slow.next;
        slow.next = prev;
        prev = slow;
        slow = next;
    }

    // 若節點數量為奇數，跳過中點
    if (fast) slow = slow.next;

    // 比較反轉後的前半部與後半部
    while (prev && slow) {
        if (prev.val !== slow.val) return false;
        prev = prev.next;
        slow = slow.next;
    }

    return true;
}

解題心法

1. 使用快慢指針法找中點

   我們使用兩個指針：slow 慢指針一次移動一步，fast 快指針一次移動兩步，這樣當快指針到終點時，慢指針就正好在鏈結串列的中點。

2. 反轉前半部分鏈結串列

   在移動快慢指針的同時，我們將慢指針經過的節點進行反轉，使前半部分的節點連結順序變成相反。這樣做的好處是我們不需要額外空間來儲存原始順序，直接原地修改鏈結串列。

3. 比較反轉的前半部分與後半部分

   若鏈結串列節點數為奇數，慢指針會在中點停留，我們可以直接略過中點開始比較。接著，我們將反轉的前半部分與後半部分逐一比較，若每個值都相同，則表示是迴文。

為什麼這樣處理？

這樣的處理方法充分利用了快慢指針的優勢來找中點，同時在找中點的過程中完成反轉，不需要額外的空間來儲存鏈結串列資料，使得解法的時間複雜度為 O(n)，而空間複雜度則是 O(1)，非常高效且簡潔。

本次要點：

• 使用快慢指針來找出鏈結串列的中點。
• 在找中點的同時反轉前半部分鏈結串列。
• 比較反轉後的前半部分與後半部分來判斷是否為迴文。

這題是不是很有趣呢？
透過這些小巧思，讓我們可以輕鬆地判斷鏈結串列是否是迴文。
希望這篇文章能夠幫助你理解這個有趣的問題，我們下次再見囉～