C++ 分析一个链表是不是回文，有什么思路么

C++ 分析一个链表是不是回文，有什么思路么

分析一个链表是否回文可以通过以下步骤来实现：

1. 找到链表中点：使用快慢指针法找到链表的中间节点。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针指向链表的中间节点（如果链表长度是奇数，则正好是中间节点；如果是偶数，则是靠近中间偏左的节点）。

2. 反转后半部分链表：从中间节点开始，将后半部分链表进行反转操作。这一步可以通过迭代或递归来实现。

3. 比较两个部分：将原始链表的前半部分（从头开始）与反转后的后半部分进行逐一比较。如果全部节点值相等，则链表是回文的；否则，不是回文的。

4. 恢复链表（可选）：根据需要，可以选择恢复链表的后半部分，使链表恢复到原始状态。

下面是一个用C++实现的示例代码：

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr;
    ListNode *curr = head;
    while (curr) {
        ListNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) {
        return true; // 空链表或单个节点的链表都是回文的
    }

    // 使用快慢指针找到中间节点
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 反转后半部分链表
    ListNode *secondHalf = reverseList(slow->next);
    
    // 比较两个部分
    ListNode *p1 = head;
    ListNode *p2 = secondHalf;
    bool isPalindrome = true;
    while (p2) {
        if (p1->val != p2->val) {
            isPalindrome = false;
            break;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    
    // 恢复链表（可选）
    slow->next = reverseList(secondHalf);

    return isPalindrome;
}

int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(2);
    head->next->next->next->next = new ListNode(1);

    if (isPalindrome(head)) {
        std::cout << "The linked list is palindrome.\n";
    } else {
        std::cout << "The linked list is not palindrome.\n";
    }

    return 0;
}