请编写算法判断链表是否为回文链表。如果是返回 true ；否则返回 false。要求：空间复杂度为O1并请分析程序的时间性能。

思路：

1.首先遍历链表，找到中间节点，可以使用快慢指针的方式。

2.将链表的后半部分翻转。

3.比较前半部分和后半部分的节点值是否相等。

4.将链表的后半部分再翻转回来。

5.返回比较结果。

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

算法实现：

bool isPalindrome(ListNode* head) {
    if(head == nullptr || head -> next == nullptr) {
        return true;
    }
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast -> next != nullptr && fast -> next -> next != nullptr) {
        slow = slow -> next;
        fast = fast -> next -> next;
    }
    ListNode* pre = nullptr;
    ListNode* cur = slow -> next;
    while(cur != nullptr) {
        ListNode* next = cur -> next;
        cur -> next = pre;
        pre = cur;
        cur = next;
    }
    while(pre != nullptr) {
        if(head -> val != pre -> val) {
            return false;
        }
        head = head -> next;
        pre = pre -> next;
    }
    return true;
}