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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {} //这个是构造函数
};*/
class PalindromeList 
{
public:
    struct ListNode* middleNode(struct ListNode* head, int* number)
{
    struct ListNode* fast = head;//快指针
    struct ListNode* slow = head;//慢指针

    while (fast && fast->next)//注意这里不能写成fast->next && fast，不这样写的目的是利用短路效应防止空指针解引用
    {
        slow = slow->next;
        fast = fast->next->next;
        (*number)++;
    }
    return slow;
}
bool chkPalindrome(struct ListNode* head)
{
    if (head == NULL)
    {
        return false;
    }
    else if (head->next == NULL)//只有一个节点的情况
    {
        return true;
    }
    //后面的链表一定是携带有两个或以上数量的节点

    //1.逆转链表
    int number = 0;
    struct ListNode* mid = middleNode(head, &number);
    struct ListNode* cache0 = mid;
    struct ListNode* cache1 = mid->next;
    struct ListNode* cache2 = NULL;
    if (cache1 && cache1->next != NULL)
    {
        cache2 = mid->next->next;
    }
    else
    {
        cache2 = NULL;
    }
    while (cache1 != NULL)
    {
        cache1->next = cache0;
        cache0 = cache1;
        cache1 = cache2;
        if (cache2 != NULL)
            cache2 = cache2->next;
    }
    //2.开始比较判断
    //最后从两端的head和cache0开始比较
    while (number)
    {
        if (head->val != cache0->val)
        {
            return false;
        }
        head = head->next;
        cache0 = cache0->next;
        number--;
    }
    return true;
}
};
//先找到中间节点再相加两个节点的val看是否为定值