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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    
    ListNode* reverse(ListNode* head)
    {
        if(head==nullptr)
        {
            return nullptr;
        }

        ListNode* cur = head;
        ListNode* pre = nullptr;

        while(cur!=nullptr)
        {
            ListNode* tmp = cur->next;
            cur->next = pre;

            pre = cur;

            cur = tmp;
        }

        return pre;
    }
    // hangmeng 一面 手撕代码时遇到过此题  当时有写错
    bool isPail(ListNode* head) {
        // write code here
        if(head==nullptr)
        {
            return false;
        }

        int n=0;

        ListNode* cur = head;
        while(cur!=nullptr)
        {
            cur = cur->next;

            n++;
        }

        int m = n/2;

        cur = head;
        for(int i=0; i<m; ++i)
        {
            cur = cur->next;
        }

        if(n%2!=0)
        {
            cur = cur->next;
        }

        ListNode* inv = reverse(cur);
        cur = head;
        for(int i=0; i<m; ++i)
        {
            if(cur->val != inv->val) return false;

            cur = cur->next;

            inv = inv->next;
        }

        return true;
    }
};

我的最终做法 O(n) O(1)