题目描述（来源）

        对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

        给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

思路

        找到传入链表的中间结点，并将中间结点及其后面结点进行反转，然后再将原链表的前半部分与反转后的后半部分进行比较，若相同，则该链表是回文结构，否则，不是回文结构。 

1.找到链表的中间结点。 

2.反转中间结点及其后面的结点。

3.比较链表的前半部分与后半部分的结点值，若相同则是回文结构，否则，不是回文结构。

将A指针指向的结点与RHead指针指向的结点进行比较，若相同，则两个指针后移，继续比较后面的结点，直到RHead指针指向NULL时，比较结束。

// 该函数的作用是找到链表的中间节点并返回
struct ListNode* middleNode(struct ListNode* head)
{
    // 初始化两个指针，slow和fast，都指向链表头节点
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    // 当fast指针及其下一个节点都不为空时，持续执行循环
    while (fast && fast->next)
    {
        // slow指针每次向前移动一个节点
        slow = slow->next;
        // fast指针每次向前移动两个节点
        fast = fast->next->next;
    }
    // 循环结束后，slow指针指向了链表的中间节点
    return slow;
}

// 该函数的作用是反转链表，并返回反转后的新链表头节点
struct ListNode* reverseList(struct ListNode* head)
{
    // 初始化一个指针cur指向原链表头节点
    struct ListNode* cur = head;
    // 初始化一个新链表头节点newhead为NULL
    struct ListNode* newhead = NULL;

    // 当cur指向的节点不为空时，持续执行循环
    while (cur)
    {
        // 保存cur节点的下一个节点
        struct ListNode* next = cur->next;
        
        // 反转cur节点的指向，使其指向新的链表头
        cur->next = newhead;

        // 更新新链表头节点为当前cur节点
        newhead = cur;

        // 移动cur指针到下一个节点
        cur = next;
    }
    // 循环结束后，newhead指向反转后的新链表头节点
    return newhead;
}

// 该函数的作用是检查链表是否为回文链表，并返回布尔值
bool chkPalindrome(ListNode* Head)
{
    // 首先找到链表的中间节点
    ListNode* mid = middleNode(Head);

    // 将中间节点之后的部分反转，得到RHead
    ListNode* RHead = reverseList(mid);

    // 用两个指针分别从头节点和反转后的链表头节点开始遍历
    while (RHead)
    {
        // 如果对应位置的节点值不相等，则链表不是回文链表，返回false
        if (Head->val != RHead->val)
            return false;

        // 两个指针分别向后移动一位
        Head = Head->next;
        RHead = RHead->next;
    }

    // 若循环结束仍未发现不相等的节点值，则链表是回文链表，返回true
    return true;
}