链表的回文结构判断
【问题描述】对于一个链表，设计一个算法判断其是否为回文结构。如果是请返回true，否则请返回false。

【输入形式】a b c # //输入以#结束
【输出形式】false //或者true
【样例输入】a #
【样例输出】true

#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

struct ListNode{
    char val;
    ListNode* next;
};
typedef ListNode* LinkList;

void createList(LinkList& L){
    L = new ListNode;
    ListNode* r = L;
    char x;
    while(cin >> x && x != '#'){ 
        ListNode* s = new ListNode;
        s->val = x;
        s->next = nullptr;
        r->next = s;
        r = s;
    }
}

void printList(LinkList L){
    ListNode* p = L->next;
    while(p){
        cout << p->val << " ";
        p = p->next;
    }
}

void deleteList(LinkList& L){
    ListNode* p = L->next;
    while(p){
        ListNode* s = p;
        p = p->next;
        delete s;
    }
    delete L;
}

bool isPalindrome(LinkList L){
    int len = 0;
    ListNode* cur = L->next; //要跳过头节点保证之后的 arr 里面没有没存入数据位置
    while(cur){
        len ++;
        cur = cur->next;
    }

    vector<char> arr(len);
    int index = 0;
    cur = L->next;
    while(cur){
        arr[index ++] = cur->val;
        cur = cur->next;
    }

    int l = 0,r = len - 1;
    while(l < r){
        if(arr[l] != arr[r]) return false;
        l ++;
        r --;
    }
    return true;
}

int main(){
    LinkList L = nullptr;
    createList(L);
    //printList(L);
    if(isPalindrome(L)) cout << "true" << endl;
    else cout << "false" << endl;
    deleteList(L);
    return 0;
}