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

// 方法一：反转后一段链表然后从两端遍历逐个判断。
class Solution {
public:
    bool isPail(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* cur1 = head;
        ListNode* cur2 = revers(slow);
        while(cur2) {
            if(cur1->val != cur2->val) 
                return false;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return true;
    }

    ListNode* revers(ListNode* head) {
        if(!head)    return head;

        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

// 方法二：用容器装链表的节点，然后双指针逐个判断
class Solution {
public:
    bool isPail(ListNode* head) {
        vector<ListNode*> vec;
        while(head) {
            vec.push_back(head);
            head = head->next;
        }
        int i=0, j = vec.size()-1;
        while(i < j) {
            if(vec[i]->val != vec[j]->val)
                return false;
            i++;
            j--;
        }
        return true;
    }
};