[数据结构与算法]234.回文链表

题目

贪心

要判断链表是否为回文，首先需要找到链表的中心点，可以采用快慢指针的方式来查找。

在查找的过程中可以用栈保存一下每个节点的信息，这样在找到后半段的数值时可以跟栈做比对来判断回文。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *slow = head, *fast = head;
        int flag = 0;
        stack<int> s;
        if(head->next==nullptr)
            return true;
        while(slow && fast) {
            s.push(slow->val);
            ++flag;
            slow = slow->next;
            if(fast->next==nullptr) // 边界条件，防止下一条语句错误
                break;
            fast = fast->next->next;
            if(fast && fast->next==nullptr) { // 防止栈保存奇数长度的链表的中心结点，因此终止循环
                slow = slow->next;
                break;
            }
        }
        while(!s.empty()) {
            if(s.top() != slow->val)
                return false;
            s.pop();
            slow = slow->next;
        }
        return true;
    }
};

递归

利用递归的特性来实现链表的倒序，以此来达到判断回文的目的。

class Solution {
public:
    bool check(ListNode* cp) {
        if(cp!=nullptr) {
            if(!check(cp->next))
                return false; // 保证 false 能够回传
            if(cp->val != fp->val)
                return false;
            fp = fp->next;
        }
        return true;
    }

    bool isPalindrome(ListNode* head) {
        fp = head;
        return check(fp);
    }
private:
    ListNode *fp; // 标记回文对应的前半结点
};