---
tags: LeetCode
---

# 234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

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

Follow up:
Could you do it in O(n) time and O(1) space?

輸入範本如下

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsPalindrome(ListNode head) {
        
    }
}

---

### 直覺想法

1. 若兩倍速走的指標走到了終點 , 則一倍速走的指標必定在整段 LinkedList 的中間. 再使用 [206. Reverse Linked List](https://hackmd.io/CC-tH5eaQmuesbWvZmN_OQ?view) 的方法 , 反轉剩下半個 List , 從頭尾兩點 , 開始走訪 , 判斷是否值都相等. 若否 , 不是迴文.

    104 ms	28 MB
    You are here!
    Your runtime beats 61.98 % of csharp submissions.
    public bool IsPalindrome(ListNode head)
    {
        ListNode turtle = head, rabbit = head;
        while (rabbit != null && rabbit.next != null)
        {
            turtle = turtle.next;
            rabbit = rabbit.next.next;
        }
        // turtle 再整段 List 的中間.
        // 反轉剩下半段 List , 並取得最後一點的 point.
        ListNode reverseStart = ReverseList(turtle);
        // 逐一比對值是否都相等. , 因為反轉的關西 , head 那頭的 list 走訪會有 cycle.
        for (; reverseStart != null; head = head.next, reverseStart = reverseStart.next)
        {
            if (head.val != reverseStart.val)
            {
                return false;
            }
        }
        return true;

        ListNode ReverseList(ListNode node)
        {
            ListNode pre = null;
            while (node != null)
            {
                ListNode next = node.next;
                node.next = pre;
                pre = node;
                node = next;
            }
            return pre;
        }
    }

2. 將所有的值都存入 List 內. 剩下就是 two point 的方式去判斷是否回文 , 會使用比上一個方式還要多的記憶體.

    100 ms	29.3 MB
    You are here!
    Your runtime beats 84.50 % of csharp submissions.
    public bool IsPalindrome(ListNode head)
    {
        List<ListNode> list = new List<ListNode>();
        for (; head != null; head = head.next)
        {
            list.Add(head);
        }

        for (int l = 0, r = list.Count - 1; l < r; l++, r--)
        {
            if (list[l].val != list[r].val)
            {
                return false;
            }
        }
        return true;
    }

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: