题解 | #链表的回文结构#

先给出一个很简单的写法，可能不满足空间复杂度是O（1），就是用栈来保存节点的数据， 第二个符合条件的解法在后面，会稍微复杂一点

首先： 1.判断栈是否是空，如果是空直接将节点数据入栈 2.如果不是空那么就判断栈顶元素是不是和当前节点值相同，如果相同就出栈，不同的话就将当前节点入栈 题目给出最多是有900个节点，所以理论上如果这个链表是回文的那么这个栈最多就存了450个节点，然后就开始出栈了。所以如果栈内的数据大于450可以直接返回false

优点在于代码非常简单，且思路也很简单 如有更优方案或者优化方法请务必在评论区指点出来！！感谢

代码如下：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        int stk[500] = {0};
        int tt = 0;
        ListNode* cur = A;
        while(cur)
        {
            if(tt > 450) return false;
            if(tt > 0)
            {
                if(stk[tt] == cur->val)
                {
                    --tt;
                }
                else
                {
                    stk[++tt] = cur->val;
                }
            }
            else
            {
                stk[++tt] = cur->val;
            }
            cur = cur ->next;
        }
        return tt==0;
    }
};

方法二：因为要判断回文，所以如果是合格的回文串，那么从中间开始向后的每个节点必定和第一个节点向后一一匹配，所以思路就是：

先找到链表的中间节点
然后将后半段链表逆序
最后同时遍历开头和中间逆序完了的链表，中间如果发生不匹配就返回false

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        //先找到中间节点
        ListNode *slow = A , *fast = A;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        //将后半部分逆置
        ListNode* cur = slow;
        ListNode* newhead = nullptr;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }
        //遍历链表进行匹配 
        while(A!=slow)
        {
            if(A->val != newhead->val)
                return false;
            A = A->next;
            newhead = newhead->next;
        }
        return true;
    }
};