//
// Created by tangs on 2018/10/8.
//

#include <iostream>

using namespace std;

struct LNode{
    char ch;
    LNode *next;
};

/**
 * 通过传入的字符串创建字符链表
 * @param str 传入的字符串
 * @return
 */
LNode *InitLink() {
    LNode *head = new LNode();
    head->ch = '\0';
    head->next = NULL;

    return head;
}

void PrintLink(LNode*L) {
    if (L == NULL) {
        return;
    }
    LNode *p = L->next;
    while (p != NULL) {
        cout << p->ch;
        p = p->next;
    }
    cout << endl;
}

bool GetValue(LNode* L, char &x) {
    if (L == NULL|| L->next ==NULL)
        return false;

    char temp = L->next->ch;
    x = temp;
    return true;
}

int DeNode(LNode* &L){
    if (L == NULL){
        return 1;
    }

    L = L->next;
    return 0;
}

bool JudgeChar(LNode* &L, char ch, int length, int number) {
    // 进栈
    if (number <= (length / 2)) {
        LNode *node = new LNode();
        node->ch = ch;
        node->next = NULL;

        LNode *p = L->next;
        node->next = p;
        L->next = node;
        return true;
    }

    // 判断长度是否是单数，单数的话，中间的字符默认合法。
    if (length % 2 != 0 && number == length / 2 + 1)
        return true;

    // 判断是否合法，然后出栈
    char tempCh;
    if (!GetValue(L, tempCh))
        return false;

    if (tempCh != ch)
        return false;

    // 出栈
    DeNode(L);
    return true;
}


bool JudgeStr(LNode* &L, string str){
    for (int i = 0;i < str.length();i ++){
        if (JudgeChar(L, str[i], str.length(), i+1)){
            continue;
        }
        return false;
    }
    return true;
}

/**
 * 设单链表的表头指针为L，节点结构由data和next两个域组成，其中data域为字符型，
 * 试设计算法判断该链表的全部n个字符是否中心对称。例如xyx,xyyx都是中心对称。
 * @return
 */
int main() {

    LNode *L = InitLink();

    string str;
//    cin >> str;

    str = "xyx";
    if (JudgeStr(L, str)) {
        cout << "legal: " << str << endl;
    } else {
        cout << "illegal: " << str << endl;
    }

    str = "xyyx";
    if (JudgeStr(L, str)) {
        cout << "legal: " << str << endl;
    } else {
        cout << "illegal: " << str << endl;
    }

//    while (cin>>str){
//        if (JudgeStr(L, str)) {
//            cout << "legal: " << str << endl;
//        } else {
//            cout << "illegal: " << str << endl;
//        }
//    }

    return 0;
}