C++ 链表回文判断算法：空间复杂度 O(1) 解法

C++ 链表回文判断算法：空间复杂度 O(1) 解法

本篇文章提供 C++ 代码实现判断链表是否为回文链表，并详细分析算法的时间复杂度和空间复杂度。该算法采用双指针和链表翻转技巧，实现空间复杂度为 O(1) 的高效解法。

题目描述:

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

时间复杂度分析:

需要遍历整个链表，时间复杂度为 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* secondHalfHead = reverseList(slow->next);
    ListNode* p1 = head;
    ListNode* p2 = secondHalfHead;
    bool result = true;
    while (p2 != nullptr) {
        if (p1->val != p2->val) {
            result = false;
            break;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    slow->next = reverseList(secondHalfHead);
    return result;
}

ListNode* reverseList(ListNode* head) {
    ListNode* newHead = nullptr;
    while (head != nullptr) {
        ListNode* nextNode = head->next;
        head->next = newHead;
        newHead = head;
        head = nextNode;
    }
    return newHead;
}