【LC】回文链表

---

题目描述：

题解一：deque

class Solution {
public:
    bool isPalindrome(ListNode* head) {
    if(head == nullptr) return false;
    //使用双端队列
    deque<int> deq;
    while(head != nullptr)
    {
        deq.push_back(head->val);
        head = head->next;
    }
    while(!deq.empty())
    {
        if(deq.front() != deq.back())
        {
            return false;
        }
        deq.pop_front();
        if(!deq.empty())
        {
             deq.pop_back();
        }
    }
    return true;
    }
};

题解二：stack

class Solution {
private:
    int getlen(ListNode* head)
    {
        int count = 0;
        while(head != nullptr)
        {
            ++count;
            head = head->next;            
        }
        return count;
    }
public:
    bool isPalindrome(ListNode* head) {
        if(head == nullptr) return false;
        stack<int> st;
        ListNode* ptr = head;
        int half_len  = getlen(head) / 2;
        bool tag = getlen(head) % 2 == 1 ? true : false;
        while(half_len--)
        {
            st.push(ptr->val);
            ptr = ptr->next;
        }
        if(tag)
        {
            ptr = ptr->next;
        }
        while(!st.empty() && ptr != nullptr && st.top() == ptr->val)
        {
            st.pop();
            ptr = ptr->next;
        }
        if(st.empty())
        {
            return true;
        }
        return false;
    }
};