題目在問什麼

給一條單向 linked list，判斷它是否為回文。

例子

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

題目的進階要求

題目追問能不能做到：

  • 時間複雜度 O(n)
  • 空間複雜度 O(1)

所以如果直接把整條 linked list 複製到陣列再雙指標比對，雖然能做，但不符合 follow-up。

解題思路

這份寫法走的是經典三步：

  1. 用快慢指標找到 linked list 中點
  2. 把後半段反轉
  3. 從前半段和反轉後的後半段同步往前比對

如果每個對應位置的值都相同，這條 linked list 就是回文。

為什麼這樣可行

快指標一次走兩步，慢指標一次走一步。當快指標到尾端時，慢指標剛好會停在中間附近。

之後把慢指標開始的後半段反轉，就能讓：

  • 前半段從頭往後走
  • 後半段從尾往前走

這兩邊在單向 linked list 上也能被線性比較。

代碼

public class Solution
{
    public bool IsPalindrome(ListNode head)
    {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null)
        {
            fast = fast.next.next;
            slow = slow.next;
        }

        fast = head;
        slow = Reverse(slow);

        while (slow != null && fast != null)
        {
            if (fast.val != slow.val) { return false; }
            fast = fast.next;
            slow = slow.next;
        }

        return true;
    }

    ListNode Reverse(ListNode node)
    {
        ListNode prev = null;
        ListNode curr = node;

        while (curr != null)
        {
            ListNode originNext = curr.next;
            curr.next = prev;
            prev = curr;
            curr = originNext;
        }

        return prev;
    }
}

複雜度

  • 時間複雜度：O(n)
  • 空間複雜度：O(1)

這題先記住的重點

  • 回文 linked list 的標準解法就是「找中點 + 反轉後半 + 對比」
  • 快慢指標是這題的基礎
  • follow-up 的重點在於不要額外開陣列或堆疊