通过快慢指针找到链表中间结点，然后反转链表的后半部分，再与前半部分进行比较来判断链表是否为回文链表

    时间复杂度O(n)
    空间复杂度O(1)

    1. class Solution {
    2. public:
    3.     bool isPalindrome(ListNode* head) {
    4.         ListNode *half = halfL(head);
    5.         ListNode *front = head;
    6.         ListNode *back = reverseL(half);
    7.         // 如果链表结点数量是偶数的话，快慢指针返回的中间结点刚好是中间两个结点的后一个结点。反转后前半部分比后半部分多一个中间结点
    8.         // 如果链表结点数量是奇数的话。快慢指针返回的中间结点刚好是中间结点。反转后前后半部分长度相同，都以中间结点结尾
    9.         // 而中间结点不会影响最后结果，所以这里的判断条件是两个结点都不为空，最后前半部分会剩下一个结点。
    10.         while (back && front) {
    11.             if (back->val != front->val) return false;
    12.             back = back->next;
    13.             front = front->next;
    14.         }
    15.         return true;
    16.     }
    17.     ListNode *halfL(ListNode *head) {
    18.         ListNode *res = nullptr;
    19.         ListNode *slow = head;
    20.         ListNode *fast = head;
    21.         while (fast && fast->next) {
    22.             slow = slow->next;
    23.             fast = fast->next->next;
    24.         }
    25.         return slow;
    26.     }
    27.     ListNode *reverseL(ListNode *head) {
    28.         ListNode *cur = head;
    29.         ListNode *pre = nullptr;
    30.         while (cur) {
    31.             ListNode *tmp = cur->next;
    32.             cur->next = pre;
    33.             pre = cur;
    34.             cur = tmp;
    35.         }
    36.         return pre;
    37.     }
    38. };