回文链表

题目链接

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

示例:

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

思路

解法一：

  1. 使用快慢指针找到中间位置；
  2. 翻转中间后面的链表；
  3. 比较两段链表节点的值，若有一个不相等，则返回 false ，否则返回 true 。
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }

        ListNode* halfNode = findHalfNode(head);
        ListNode* startNode = reverseList(halfNode->next);

        // 判断是否是回文
        ListNode* p1 = head;
        ListNode *p2 = startNode;
        bool result = true; 
        while (result && p2!= nullptr) { // 使用标志，若出现一次false，则直接退出循环
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }

        halfNode->next = reverseList(startNode); //将翻转的链表恢复
        return result;
    }

    // 翻转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

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