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

#include <iostream>
#include<stack>
#include<vector>
#include<algorithm>
#include<list>
using namespace std;
//链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode():val(0),next(nullptr){}
    ListNode(int x):val(x),next(nullptr){}
    ListNode(int x,ListNode* next):val(x),next(next){}
};
//初始化插入数据
ListNode* Init() {
    ListNode* head=new ListNode(-1);
    ListNode* tmp=head;
    int n;
    int x;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        ListNode* newNode = new ListNode(x);
        tmp->next = newNode;
        tmp = tmp->next;
    }
    return head->next;
}
//打印链表
void PrintList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
}

class Solution {
public:
    Solution() {
    }
    bool check(ListNode* head) {
        vector<int> arr;
        while (head != nullptr) {
            arr.push_back(head->val);
            head = head->next;
        }
        int i = 0;
        int j = arr.size() - 1;
        while (i <= j) {
            if (arr[i++] != arr[j--]) return false;
        }
        return true;
    }
};

int main() {
    Solution s;
    ListNode* head = Init();
    //PrintList(head);
    bool flag=s.check(head);
    if (flag) cout << "true" << endl;
    else cout << "false" << endl;
    return 0;
}