链表——回文链表

回文链表

---

这个题属实不算难，但是因为出在链表部分，很容易让人误会是使用链表的特性来解题，但是实际上还是使用普通的回文串判别的算法。我第一次在想的时候想了半天怎么用单向链表的特性来解，结果发现是不行的。

主要算法就是先遍历一遍链表保存到其他能随机访问的数据结构中，然后再用两个指针（广义的）一个指头一个指尾，向中间逼近的同时比较两个指针指向内容的值。

---

下面就是两个比较好的算法：

#include<stack>
using namespace std;
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> s;
        ListNode* now=head;
        while(now!=NULL){
            s.push(now->val);
            now=now->next;
        }
        
        now=head;
        while(now!=NULL){
            if(s.top()!=now->val){
                return false;
            }
            s.pop();
            now=now->next;
        }
        return true;
    }
};

这个就是利用栈的特性比较链首元素和栈顶元素（最后入栈的元素即链尾元素），然后链指针向后移，同时出栈一个元素，算法虽然挺好的但是实际速度不如用最普通的数组...

class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        vector<int> vals;
        while(head)
        {
            vals.push_back(head->val);
            head = head->next;
        }
        for(int i = 0; i<vals.size()/2;++i )if(vals[i]!=vals[vals.size()-1-i])return 0;
        return 1;
    }
};

这个就是之前提到的最简单的不断比较首元素和尾元素，相信都能很容易理解。