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

1. 解法1:翻转链表，用vector存储正序和逆序的结果，看看两个vector是否相等 38ms

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    //反转链表
    ListNode* ReverseList(ListNode* pHead)
    {
        if(!pHead)
            return pHead;
        ListNode *pre = nullptr;
        ListNode *curr = pHead;
        while(curr)
        {
            ListNode *temp = curr->next;
            curr->next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }
    bool isPail(ListNode* head) {
        // write code here
        ListNode *p = head;
        vector<int> v1;
        vector<int> v2;
        while(p)
        {
            v1.push_back(p->val);
            p = p->next;
        }
        head = ReverseList(head);
        while(head)
        {
            v2.push_back(head->val);
            head = head->next;
        }
        if(v1 == v2)
            return true;
        else
            return false;
    }
};

2.解法2：利用栈先进后出的特性来判断正逆序是否相等 41ms

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        stack<ListNode*> s;
        ListNode* curr = head;
        while(curr)
        {
            s.push(curr);
            curr = curr->next;
        }
        while(head)
        {
            if(head->val != s.top()->val)
                return false;
            s.pop();
            head = head->next;
        }
        return true;
    }
};

3. 解法3：快慢指针+翻转链表

    将后半部分的链表倒置，然后这个链表链表分别从两点开始遍历，对比元素是否是相等;  39ms

        if(!head || !head->next)
            return true;
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* reverseHead = ReverseList(slow->next);
        while(head && reverseHead)
        {
            if(head->val!=reverseHead->val)
                return false;
            head = head->next;
            reverseHead = reverseHead->next;
        }
        return true;