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

本文将介绍一种 C++ 算法，用于判断单链表是否为回文链表。该算法的空间复杂度为 O(1)，并附带详细的时间性能分析和代码示例。

思路

找到链表中点，可以使用快慢指针，当快指针到达链表末尾时，慢指针指向中间节点。
反转链表后半部分。
将前半部分和后半部分进行比较，判断是否为回文链表。

时间复杂度

O(n)，其中 n 为链表长度。需要遍历链表找到中点，反转链表后半部分，以及比较前半部分和后半部分，都是一次遍历，因此总时间复杂度为 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;
}

希望本文能够帮助您理解 C++ 链表回文判断算法，并能将其应用于实际问题中。