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

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    ListNode * reverseList(ListNode *head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode *nxt = head->next;
        ListNode *newhead = reverseList(nxt);
        nxt->next = head;
        head->next = nullptr;
        return newhead;
    }
    
    bool isPail2(ListNode *l1, ListNode *l2) {
        if (!l1) {
            return true;
        }
        return l1->val == l2->val ? isPail2(l1->next, l2->next): false;
    }

    bool isPail(ListNode* head) {
        if (!head || !head->next) {
            return true;
        }
        ListNode *bef = nullptr;
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast && fast->next) {
            bef = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        bef->next = nullptr;
        slow = reverseList(slow);
        return isPail2(head, slow);
    }
};

思路：先反转后比较。

找到链表中点，将后面的链表翻转过来，然后判断两个链表是否相等。

链表节点个数可能为奇数，导致后面的链表节点个数多一个，所以判断条件改变一下：前面的链表为空即可返回true。