Written by Allen Zhao（赵正阳）, in 11.6 0:45, 2019

1. 原题

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

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

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 思路一：转为数组，然后双向遍历

这个是最为暴力的解法。

逻辑很简单：将链表的数字用数组h存放，然后利用数组按秩访问的特性，设置两个指针，一个从前往后遍历的前指针i，另一个从后往前的后指针j，两个指针开始往两头跑，每次进一步。停止的条件如下：

1. 碰到h[i] != h[j]的情况，立即返回false，本题得解；
2. 碰到前指针跑到后指针的后面的情况，或两针相遇，即i >= j，这时很明显，都已经相遇或相遇过了，证明它们在检验回文数的路上没有错，返回true，本题得解。

本题的复杂度分析如下：

1. 空间复杂度是O(n)，因为额外申请了一个数组的空间;
2. 时间复杂度是O(n)。
3. 虽然最终返回了正确的题解，但由于我们是通过转换数组的方法来，不是本题考察重点，也没有完全达到“进阶”中的要求。

代码实现如下（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) // 特殊情况：如果只有一个元素或者是一个空表
            return true; // 直接返回true
        
        vector<int> h; // 构建动态数组（C++中的向量）h
        while(head != nullptr){ // 通过遍历转化为数组
            h.push_back(head -> val);
            head = head -> next;
        }
        
        const int L = h.size(); // 求数组长度
        int i = 0;  // 左指针，从索引0位置开始跑
        int j = L - 1; // 右指针，从最后一个秩开始跑
        
        while(i < j){ // 只要i一直在j前面
            if(h[i] != h[j]) // 一旦发现值不等
                return false; // 直接返回false
            
            ++i; // i往前走一步
            --j; // j向后走一步
        }
        
        return true;
    }
};

3. 思路2：评论区看到的思路

我不知道如何解释，还有请各位大神来解释一下

# 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