题解 | #牛群编号的回文顺序# 判断回文串

知识点

回文串

思路

这道题需要判断链表的值是不是构成了回文串。

遍历链表，取出这些值，然后判断是不是回文即可。

时间复杂度

只需要遍历链表若干次 时间复杂度为

vector单次在尾部插入元素的均摊复杂度是，插入n次为

总体时间复杂度为

AC code （C++）

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return bool布尔型
     */
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        auto p = head;
        while (p) {
            vals.push_back(p->val);
            p = p->next;
        }
        for (int i = 0, j = (int)vals.size() - 1; i < j; i ++, j --) {
            if (vals[i] != vals[j]) return false;
        }
        return true;
    }
};