题解 | #链表的回文结构# c - 不带哨兵卫

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//大体思路，第一步：先求出中间节点（偶数个节点则为第二个）；
//第二步：把后半段链表逆置；
//第三步：链表两头一起往中间遍历，直到走到中间节点为止。如果有val不相等，则不是回文结构

//求中间节点函数
struct ListNode* middlleNode(struct ListNode* Head)
{
    struct ListNode* cur = Head;
    int len = 1;
    if(!Head)
        return NULL;
    while(cur)
    {
        cur = cur->next;
        len++;
    }
    
    len = len / 2 + 1;
    cur = Head;
    if(len%2 == 0)
    {
        while(--len)
          cur = cur->next;
    }
    else
    {
        while(len--)
            cur = cur->next;
    }
    return cur;
}

//逆置链表函数，采取前后指针方法
struct ListNode* reverseList(struct ListNode* Head)
{
    struct ListNode* prev, *cur;
    cur = Head;
    prev = NULL;
    
    while(cur)
    {
        struct ListNode* next;  // 保存原指针节点关系，存一个，改一次
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

//判断回文（对称逻辑）
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        
        struct ListNode* mid = middlleNode(A);
        struct ListNode* tail = reverseList(mid);
        
        while(tail != mid)
        {
            if(tail->val != A->val)
                return false;
            tail = tail->next;
            A = A->next;
        }
        return true;
        
    }
};