Written by Allen Zhao（趙正陽(yáng)）, in 11.6 0:45, 2019

1. 原題

請(qǐng)判斷一個(gè)鏈表是否為回文鏈表。

示例 1:

輸入: 1->2
輸出: false

示例 2:

輸入: 1->2->2->1
輸出: true

進(jìn)階：
你能否用 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？

來(lái)源：力扣（LeetCode）
鏈接
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 思路一：轉(zhuǎn)為數(shù)組，然后雙向遍歷

這個(gè)是最為暴力的解法。

邏輯很簡(jiǎn)單：將鏈表的數(shù)字用數(shù)組h存放，然后利用數(shù)組按秩訪問(wèn)的特性，設(shè)置兩個(gè)指針，一個(gè)從前往后遍歷的前指針i，另一個(gè)從后往前的后指針j，兩個(gè)指針開(kāi)始往兩頭跑，每次進(jìn)一步。停止的條件如下：

1. 碰到h[i] != h[j]的情況，立即返回false，本題得解；
2. 碰到前指針跑到后指針的后面的情況，或兩針相遇，即i >= j，這時(shí)很明顯，都已經(jīng)相遇或相遇過(guò)了，證明它們?cè)跈z驗(yàn)回文數(shù)的路上沒(méi)有錯(cuò)，返回true，本題得解。

本題的復(fù)雜度分析如下：

1. 空間復(fù)雜度是O(n)，因?yàn)轭~外申請(qǐng)了一個(gè)數(shù)組的空間;
2. 時(shí)間復(fù)雜度是O(n)。
3. 雖然最終返回了正確的題解，但由于我們是通過(guò)轉(zhuǎn)換數(shù)組的方法來(lái)，不是本題考察重點(diǎn)，也沒(méi)有完全達(dá)到“進(jìn)階”中的要求。

代碼實(shí)現(xiàn)如下（C++）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == nullptr || head -> next == nullptr) // 特殊情況：如果只有一個(gè)元素或者是一個(gè)空表
            return true; // 直接返回true
        
        vector<int> h; // 構(gòu)建動(dòng)態(tài)數(shù)組（C++中的向量）h
        while(head != nullptr){ // 通過(guò)遍歷轉(zhuǎn)化為數(shù)組
            h.push_back(head -> val);
            head = head -> next;
        }
        
        const int L = h.size(); // 求數(shù)組長(zhǎng)度
        int i = 0;  // 左指針，從索引0位置開(kāi)始跑
        int j = L - 1; // 右指針，從最后一個(gè)秩開(kāi)始跑
        
        while(i < j){ // 只要i一直在j前面
            if(h[i] != h[j]) // 一旦發(fā)現(xiàn)值不等
                return false; // 直接返回false
            
            ++i; // i往前走一步
            --j; // j向后走一步
        }
        
        return true;
    }
};

3. 思路2：評(píng)論區(qū)看到的思路

我不知道如何解釋，還有請(qǐng)各位大神來(lái)解釋一下

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        s1, s2, t = 0, 0, 1

        while(head):
            s1 = 10 * s1 + head.val
            s2 += t * head.val
            t *= 10
            head = head.next
        
        return s1 == s2