234.回文链表.md

// 自己用栈实现的解法
// 先遍历一遍链表获取长度，然后再重新遍历一半入栈，遍历后一半出栈对比消消乐
// 奇偶分开处理
class Solution {
public:
    stack<ListNode*> stk;  // 声明一个栈用于存储节点指针

    // 获取链表长度
    int getLength(ListNode* head) {
        ListNode* cur = head;
        int length = 0;
        while (cur) {
            length++;
            cur = cur->next;
        }
        return length;
    }

    // 判断链表是否为回文链表
    bool isPalindrome(ListNode* head) {
        ListNode* cur = head;

        int length = getLength(head);  // 获取链表长度
        int half_length = length / 2;  // 计算链表长度的一半
        bool is_odd = false;
        if (length % 2)
            is_odd = true;  // 判断链表长度是否为奇数
        else
            is_odd = false;

        int step = 0;
        while (cur) {
            step++;
            if (step == (half_length + 1) && is_odd == true) {
                cur = cur->next;
                continue;
            }

            if (step > half_length) {  // 到达后半部分节点
                int val = stk.top()->val;
                if (val != cur->val) {
                    return false;  // 值不相等，不是回文链表
                } else {
                    stk.pop();  // 值相等，出栈继续比较下一个节点
                }
            } else {
                stk.push(cur);  // 将前半部分节点指针入栈
            }
            cur = cur->next;
        }

        return true;  // 是回文链表
    }
};


// leetcode官方：遍历链表复制到数组中，然后用数组前后指针i、j夹逼判断是否是回文。
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;  // 用于存储链表节点值的向量

        // 遍历链表，将节点值存入向量
        while (head != nullptr) {
            vals.emplace_back(head->val);
            head = head->next;
        }

        // 使用双指针判断向量是否为回文
        for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) { // for循环第1段和第3段，可以打逗号
            if (vals[i] != vals[j]) {
                return false;  // 值不相等，不是回文链表
            }
        }

        return true;  // 是回文链表
    }
};

// leetcode官方：O(1)空间复杂度，快慢双指针
// endOfFirstHalf()值得学习，为了找点链表的中点，其实不需要先遍历一遍获取length，然后再遍历一半，这样还要区分奇偶。
// 直接用fast/slow，fast=fast->next->next,slow=slow->next遍历一遍，最后返回slow就是链表的中点。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        // 判断是否回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }        

        // 还原链表并返回结果
        firstHalfEnd->next = reverseList(secondHalfStart);
        return result;
    }

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

    ListNode* endOfFirstHalf(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;
    }
};