回文链表

描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true
示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这个问题的解决方案是使用快慢指针法找到链表的中点，然后反转链表的后半部分，最后比较前半部分和后半部分是否相等。

具体来说，我们可以先检查链表是否为空或只有一个节点。如果是这种情况，那么它一定是回文的。接下来，我们使用快慢指针法找到链表的中点。我们可以使用两个指针，一个慢指针和一个快指针。慢指针每次移动一个节点，而快指针每次移动两个节点。当快指针到达链表的末尾时，慢指针将指向链表的中点。

接下来，我们将反转链表的后半部分。我们可以使用三个指针，一个指向当前节点，一个指向前一个节点，一个指向下一个节点。我们可以使用类似于反转数组的方法来反转链表。

最后，我们比较前半部分和后半部分是否相等。我们可以使用两个指针，一个指向链表的头部，一个指向反转后的链表的头部。我们将它们逐个比较，如果它们不相等，则链表不是回文的。如果我们成功比较了所有的节点，则链表是回文的。

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 如果链表为空或只有一个节点，则它是回文的
        if (head == NULL || head->next == NULL) {
            return true;
        }
        
        // 使用快慢指针法找到链表的中点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 反转链表的后半部分
        ListNode* prev = NULL;
        ListNode* curr = slow->next;
        while (curr != NULL) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        // 比较前半部分和后半部分是否相等
        ListNode* p1 = head;
        ListNode* p2 = prev;
        while (p2 != NULL) {
            if (p1->val != p2->val) {
                return false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        
        return true;
    }
};

==需要注意==：两个中间节点时（链表长度为偶数），返回第二个中间节点，此时快指针可以前进的条件是当前快指针和当前快指针的下一个节点都非空；返回第一个中间节点时，此时快指针可以前进的条件是当前快指针的下一个节点和当前快指针的下下一个节点都非空。很明显，我们这里：如果奇数个节点，则第二条链表是中间节点的下一个加点；如果是偶数个节点，需要返回第一个中间节点，则第二条链表是中间节点的下一个节点。因此，这里的找中点判断条件为：while (fast->next != NULL && fast->next->next != NULL)。