---
title: "234. Palindrome Linked List"
url: "https://laigary.com/interview/coding/234-palindrome-linked-list"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-28"
tags: ["Linked List", "Palindrome", "Two Pointers", "Classic"]
---

# 234. Palindrome Linked List

[234\. Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/)

判斷一條鏈結串列是不是回文。

## 思路

這一題是一道簡單的題目，可是其實很容易不小心踩到雷。

### 直覺解：反轉之後比對

第一個直覺的想法會是我們就把 Linked List 反轉，接著比較一下是不是都一樣就好。

**可是這裡有個雷**：如果我們要反轉 Linked List，第一件要做的事情會是我們要先**複製**一個原先的 Linked List —— 不然 Linked List 都是傳指標，反轉完原先的 Linked List 就沒了，根本沒東西可以拿來比對。

這個「反轉會就地破壞原本的資料」是鏈結串列題和陣列題最不一樣的地方。陣列可以 `arr[::-1]` 得到一份新的，串列的反轉預設是原地的。

### 只比一半就夠

不過這一題其實存在著更優的解法，雖然理論時間複雜度並沒有真的改變非常多，可是**少使用了很多的記憶體**。

回文的題目的特性之一，就是前後對稱，所以我們其實並不用比對到整個 Linked List，只要比對到一半就好。可是 Linked List 並沒有長度的概念，所以可以利用快慢指針的方式取得中間點（見 [876. Middle of the Linked List](/interview/coding/876-middle-of-the-linked-list)）。

第二步就是我們從中間點到結尾的部分，反轉整個 Linked List（見 [206. Reverse Linked List](/interview/coding/206-reverse-linked-list)），這樣的話我們就會有兩個**「幾乎」**一模一樣的 Linked List。接下來和上面的部分一樣，一起齊步走，如果中間有一個位置發生不同的值，那就不是回文。

所以這題其實是**兩個已知題拼起來的**：找中點（876）+ 反轉（206）+ 齊步比對。面試時先把這三步講出來，再各自實作，比直接動手穩得多。

### 奇數長度要特判嗎

上面說「幾乎」一模一樣，就是在指這件事：回文的長度是奇數還是偶數，處理起來會不會不同？

**不用特判。** 但理由不是「中間那個元素沒被檢查到」—— 實際跑一遍會看到它**有**被檢查，只是**拿自己跟自己比**：

```text
[1, 2, 3, 2, 1] 的比較過程
（node.val, head.val, 是不是同一個節點）

  (1, 1, 不同節點)
  (2, 2, 不同節點)
  (3, 3, 同一個節點)   ← 中間的 3，自己跟自己比，必然相等
```

因為 `middleNode` 在奇數長度時回傳的是**正中間**那一顆，它同時是「前半段的最後一顆」和「反轉後那段的最後一顆」。所以最後一輪比較的兩個指針指向同一個節點，必定相等，答案不受影響。

偶數長度時前後兩段長度相同，沒有這個交會點，更單純。**兩種情況都不用寫額外的判斷**，這是這個解法漂亮的地方。

## 解題方向

### 解法一：複製一份再反轉

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def cloneLinkedList(self, head) -> ListNode:
        copy = copy_head = ListNode(0)
        curr = head
        while curr:
            copy.next = ListNode(curr.val)
            copy = copy.next
            curr = curr.next
        return copy_head.next

    def reverseList(self, head: ListNode) -> ListNode:
        node = None
        while head:
            tmp = head.next
            head.next = node
            node = head
            head = tmp
        return node

    def isPalindrome(self, head: ListNode) -> bool:
        cloned = self.reverseList(self.cloneLinkedList(head))
        curr = head

        while curr:
            if curr.val != cloned.val:
                return False
            curr = curr.next
            cloned = cloned.next
        return True
```

`cloneLinkedList` 裡的 `copy_head` 是 dummy head，讓「接第一顆」不用寫特例。

### 解法二：找中點 + 反轉後半（$O(1)$ 空間）

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # 206. Reverse Linked List
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        while head:
            tmp = head.next
            head.next = prev
            prev = head
            head = tmp
        return prev
    # 876. Middle of the Linked List
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def isPalindrome(self, head: ListNode) -> bool:
        mid = self.middleNode(head) 
        node = self.reverseList(mid)

        while node:
            if node.val != head.val:
                return False
            node = node.next
            head = head.next

        return True
```

迴圈條件是 `while node` 而不是 `while head` —— 反轉後那一段比較短（或一樣長），用它當終止條件才不會走過頭。

## 補充

### 這個解法會破壞輸入

解法二把後半段就地反轉了，跑完之後從原本的 `head` 走出來只剩前半段。`[1, 2, 3, 2, 1]` 跑完會變成 `[1, 2, 3]`。

**面試時這一定會被問**：「你的函式改動了呼叫端的資料，這樣可以嗎？」主動說出來比被抓到好，而且復原很簡單 —— **把反轉過的那段再反轉一次接回去**：

```python
    def isPalindrome(self, head: ListNode) -> bool:
        mid = self.middleNode(head)
        second = self.reverseList(mid)

        node, curr = second, head
        ok = True
        while node:
            if node.val != curr.val:
                ok = False
                break
            node = node.next
            curr = curr.next

        self.reverseList(second)     # 復原
        return ok
```

注意這裡不能中途 `return False` 了，要用一個 `ok` 記著、跑完復原再回傳，否則提早離開就漏掉復原。

### 最短的寫法

如果不在意空間，把值全部倒進 list 再比對是最短的：

```python
    def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        while head:
            vals.append(head.val)
            head = head.next
        return vals == vals[::-1]
```

三行，$O(n)$ 時間 $O(n)$ 空間，而且**不會破壞輸入**。面試時可以先寫這個確認方向，再說「如果要 $O(1)$ 空間我會改成找中點 + 反轉後半」—— 這樣的順序比一開始就寫複雜版更能展示思考過程。

### 相關題

[876. Middle of the Linked List](/interview/coding/876-middle-of-the-linked-list)、[206. Reverse Linked List](/interview/coding/206-reverse-linked-list) 是這題的兩個零件；[143. Reorder List](/interview/coding/143-reorder-list) 是另一個用同樣兩個零件拼起來的題目（找中點、反轉後半、交錯合併）。**「找中點 + 反轉後半」是鏈結串列的一組常用組合技**，見 [Linked List 模板](/interview/coding/linked-list-template)。

## 複雜度

**倒進 list 比對**
- 時間 $O(n)$ — 一趟收集、一趟比對
- 空間 $O(n)$ — 存下所有值

**複製一份再反轉**
- 時間 $O(n)$ — 複製、反轉、比對各一趟
- 空間 $O(n)$ — 完整複製一條串列（連節點物件都新建，比上一種更耗）

**找中點 + 反轉後半**
- 時間 $O(n)$ — 找中點 $O(n)$、反轉 $O(n/2)$、比對 $O(n/2)$
- 空間 $O(1)$ — 只有幾個指針

其中 `n` 是節點數。

三者時間同級，**差別完全在空間** —— 這也是題目 follow-up 問的（"Could you do it in O(n) time and O(1) space?"）。代價是它會就地修改串列，所以嚴謹的做法要加上復原。