题解 | #判断一个链表是否为回文结构#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <bits/types/stack_t.h>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    // 虽然能过，但是我自己感觉怪怪的，不知道哪里不对劲，这个还是别看了
    // bool isPail(ListNode* head) {
    //     if(head->next==nullptr) return true;
    //     ListNode* slow = head;
    //     ListNode* fast = head;
    //     stack<int> st;
    //     while (fast && fast->next) {
    //         st.push(slow->val);
    //         slow = slow->next;
    //         fast = fast->next->next;
    //     }
    //     cout<<"st.top() : "<< st.top() << "   slow->val"<< slow->val<<endl;
    //     while(slow && !st.empty()) {

    //         if(st.top() == slow->val) {
    //             st.pop();
    //         }
    //         slow=slow->next;
    //     }
    //     if(st.empty()) {
    //         return true;
    //     }
    //     return false;
    // }
  	// 方式一
    //1.用快慢指针找到中点，然后借助判断回文，这里需要注意链表长度为奇数的时候，此时慢指针指向链表的中间节点，需要再向前走一步
    // bool isPail(ListNode* head) {
    //     ListNode* slow = head;
    //     ListNode* fast = head;
    //     stack<int> st;
    //     // while (fast->next && fast->next->next) {
    //     while(fast && fast->next) {
    //         st.push(slow->val);
    //         slow = slow->next;
    //         fast = fast->next->next;
    //     }
    //     if(fast){ //链表长度为奇数的时候，慢指针需要多走一步，即走过中间节点
    //         slow = slow->next;
    //     }
    //     while (slow) {
    //         if(st.top() != slow->val){
    //             return false;
    //         }
    //         slow = slow->next;
    //         st.pop();
    //     }
    //     if(st.empty()){
    //         return true;
    //     }
    //     else{
    //         return false;
    //     }
    // }
	// 方式二
    bool isPail(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* pre = nullptr;
        while (fast && fast->next) {
            fast = fast->next->next;
            // slow = slow->next 就在这四句代码中实现了,同时实现了反转前半部分链表
            ListNode* next = slow->next;
            slow->next = pre;
            pre = slow;
            slow = next;
        }
        if (fast) slow = slow->next;
        while (slow) {
            if (pre == nullptr || pre->val != slow->val) {
                return false;
            }
            pre = pre->next;
            slow = slow->next;
        }
        return true;
    }
};