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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    ListNode *reserve_node(ListNode* head){
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur != nullptr){
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next; 
        }
        return pre;
    }
//将回文的后半部分反转后的部分和前半部分作比较
    bool isPail(ListNode* head) {
        int len = 0;
        ListNode* tmp = head;
        ListNode* cur = head;
        
        while(tmp != nullptr){
            len++;
            tmp = tmp->next;
        } 
        int mid_num = len / 2; 
        ListNode* mid = head;
        while(mid_num--){
            mid = mid->next;
        }
       
        mid = reserve_node(mid);
        while(mid != nullptr){
            if(cur->val != mid->val){
                return false;
            }
            cur = cur->next;
            mid = mid->next;
        }
        return true;
    }
};