qiaoxu123
1/9/2019 - 3:33 AM

234. Palindrome Linked List

考察链表遍历 由于链表的特性，访问只能顺序访问。

  • Approach 1 ： Array

如果考虑额外空间，可以使用数组存储后然后头尾对照判断，和字符串的判断基本相同。

  • Approach 2 : recursive

通过递归的形式进行比较

myCode.cpp
content_copyfile_download
//20ms  50%

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next)
            return true;
        vector<int> array;
        array.push_back(head->val);
        while(head->next != NULL){
            head = head->next;
            array.push_back(head->val);
        }
        // cout << array.size();
        for(int i = 0,j = array.size()-1;i < j;++i,--j)
            if(array[i] != array[j])
                return false;
        return true;
    }
};
recursive.cpp
content_copyfile_download
//20 ms 

class Solution {
public:
    ListNode* temp;
    bool isPalindrome(ListNode* head) {
        temp = head;
        return check(head);
    }
    
    bool check(ListNode* p){
        if(NULL == p) return true;
        bool isPal = check(p->next) & (temp->val == p->val);
        temp = temp->next;
        return isPal;
    }
};