# [234. Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/description/)
## 1. 題目說明
- **有一個==鏈結串列==**
- **該鏈接串列的資料皆為==0 ~ 9 的整數==**
- **要判斷該鏈結串列是否為回文數**
- **是回文數則回傳 ==True==，反之回傳 ==False==**
## 2. 解題思路1
1. **製作兩個鏈結串列：**
- **一個存放==原本==的鏈結串列**

    flowchart LR
    A([A])-->B([B])-->C([C])-->D([D])

- **一個存放==反向鏈結==的鏈接串列**

    flowchart RL
    A([D])-->B([C])-->C([B])-->D([A])

2. **若兩個鏈結串列的所有資料皆相同，代表==是回文數==**
3. **若兩個鏈結串列有資料不相同，代表==不是回文數==**
### ● 程式碼

bool isPalindrome(struct ListNode* head) {
    // 初始化兩鏈結串列
    struct ListNode* reg = NULL;
    struct ListNode* ptr = head;
    // 設定反向鏈結的鏈結串列
    while (ptr != NULL) {
        struct ListNode* p = malloc(sizeof(struct ListNode));
        p->val = ptr->val;
        p->next = reg;
        reg = p;
        ptr = ptr->next;
    }
    // 檢查是否是回文數
    while (reg != NULL) {
        if (reg->val != head->val)
            return false;
        struct ListNode* t = reg;
        reg = reg->next;
        head = head->next;
        free(t);
    }
    return true;
}

---
## 3. 解題思路2
1. **我們可以先計算鏈結串列的==總長度==**
2. **再把鏈結串列分成==前、後兩段==**
- **==前段==：所有結點的鏈結方向要==反向==**
- **==後段==：所有節點的鏈結方向==不變==**
- **示意圖**

flowchart LR
    a([n0]) --> 
    b([n1]) --> 
    c([n2]) -->
    d([n3])

flowchart RL
    subgraph A[ ]
        direction RL
        b([n1]) --> 
        a([n0])
    end
    subgraph B[ ]
        direction LR
        c([n2]) -->
        d([n3])
    end
    B:::null
    A:::null
    B ~~~ A
    
    classDef null stroke:#fff,fill:#fff

- **判斷回文數只需從 ==`n1、n2`== 開始判斷就可以呵**
### ● 程式碼

bool isPalindrome(struct ListNode* head) {
    //計算鏈結大小
    int size = 0;
    struct ListNode* reg1 = head;
    struct ListNode* reg2 = head;
    while (reg1) {
        size++;
        reg1 = reg1->next;
    }
    
    struct ListNode* reg = NULL;
    reg1 = head;
    int mid = size / 2 + size % 2; //中間結點的位置
    //設定反向鏈結串列
    for (int i = 0; i < mid; i++) {
        //node順序
        //reg2 <-- reg <-- reg1
        reg = reg1;
        reg1 = reg1->next;
        //設定反向鏈結串列
        if (reg != reg2) {
            reg->next = reg2;
            reg2 = reg;
        }
    }
    //如果有奇數個node，中間會多一個node
    if (size % 2)
        reg2 = reg2->next;
    //判斷回文數
    for (int i = 0; i < size / 2; i++) {
        if (reg1->val != reg2->val)
            return false;
        reg1 = reg1->next;
        reg2 = reg2->next;
    }
    return true;
}