#define ElemType int

 class LNode {

 public:

     LNode(ElemType ele, LNode *pointer) :data(ele), next(pointer) {

     }

     LNode(ElemType ele) {

         data = ele;

         next = nullptr;

     }

     LNode() {

         data = ;

         next = nullptr;

     }

     ElemType data;

     LNode *next;

 };

 class LinkList {

 public:

     LinkList() {

         head = nullptr;

     }

     // 初始化时，创建一个长度为len的链表

     LinkList(int len) {

         head = nullptr;

         this->LListAddNodes(len);

     }

     ~LinkList() {

         this->LListDestory();

     }

     LNode *LListHead() {

         return head;

     }

     // 设置链表头结点

     void LListSetHead(LNode *node) {

         head = node;

     }

     // 获取链表长度

     int LListLength();

     // 判断链表是否为空

     bool LListEmpty() {

         return(head == nullptr) ? true : false;

     }

     // 返回链表中第pos个结点

     bool GetNode(int pos, LNode **node);

     // 返回指定data在链表中第一次出现的位置

     bool LocateNode(ElemType ele, LNode **node);

     // 在指定位置插入后一个结点，但若pos为0是表示在链表头插入一个结点

     bool LListInsert(int pos, LNode *node);

     // 删除指定位置结点

     bool LListDelete(int pos);

     // 删除指定位置结点并返回被删除结点的信息

     bool LListDelete(int pos, LNode *node);

     // 遍历线性表

     void LListTraverse();

     // 在链表尾添加cnt个结点

     bool LListAddNodes(int cnt);

     // 销毁链表，释放所有结点资源

     void LListDestory();

 private:

     LNode *head;

 };

 int LinkList::LListLength()

 {

     int cnt = ;

     LNode *node = head;

     while (node != nullptr) {

         cnt++;

         node = node->next;

     }

     return cnt;

 }

 bool LinkList::GetNode(int pos, LNode **node)

 {

     if (pos > this->LListLength() || pos < )

         return false;

     LNode *cur = head;

     for (int i = ; i <= pos; i++) {

         cur = cur->next;

     }

     *node = cur;

     return true;

 }

 bool LinkList::LocateNode(ElemType ele, LNode **node)

 {

     LNode *curNode = head;

     while (curNode != nullptr) {

         if (curNode->data == ele) {

             *node = curNode;

             return true;

         }
            curNode = curNode->next;

     }

     return false;

 }

 bool LinkList::LListInsert(int pos, LNode *node)

 {

     // 插入位置错误

     if (pos <  || pos > this->LListLength())

         return false;

     if (pos == ) {

         node->next = head;

         head = node;

     }

     else {

         LNode *temp = nullptr;

         this->GetNode(pos, &temp);

         node->next = temp->next;

         temp->next = node;

     }

     return true;

 }

 bool LinkList::LListDelete(int pos)

 {

     if (pos < || pos > this->LListLength())

         return false;

     if (pos == ) {     // 删除头结点

         LNode *temp = head;

         head = temp->next;

         delete(temp);

     }

     else {

         LNode *temp_1 = nullptr;

         LNode *temp_2 = nullptr;

         this->GetNode(pos - , &temp_1);  // 获取被删除结点的前一个结点

         temp_2 = temp_1->next;

         temp_1->next = temp_2->next;

         delete(temp_2);

     }

     return true;

 }

 // 删除结点立即释放结点所占用的空间，被返回的仅仅是被删除结点的信息

 bool LinkList::LListDelete(int pos, LNode *node)

 {

     if (pos < || pos > this->LListLength())

         return false;

     if (pos == ) {

         LNode *temp = head;

         head = temp->next;

         node->data = temp->data;

         node->next = temp->next;

         delete(temp);

     }

     else {

         LNode *temp_1 = nullptr;

         LNode *temp_2 = nullptr;

         this->GetNode(pos - , &temp_1);

         temp_2 = temp_1->next;

         temp_1->next = temp_2->next;

         node->data = temp_2->data;

         node->next = temp_2->next;

         delete(temp_2);

     }

     return true;

 }

 void LinkList::LListTraverse()

 {

     LNode *curNode = head;

     while (curNode != nullptr) {

         std::cout << curNode->data << std::endl;

         curNode = curNode->next;

     }

 }

 bool LinkList::LListAddNodes(int cnt)

 {

     //std::cout << cnt << std::endl;

     if (cnt < )

         return false;

     else if (cnt == )

         return true;

     LNode *curNode = head;

     if (curNode != nullptr) {

         // 找到链表尾结点

         while (curNode->next != nullptr) {

             curNode = curNode->next;

         }

         for (int i = ; i < cnt; i++) {

             int temp;

             std::cin >> temp;

             LNode *node = new LNode(temp);

             if (!node) {

                 return false;

             }

             //node->next = nullptr;

             //node->data = i;

             curNode->next = node;

             curNode = node;

         }

     }

     else {

         int temp;

         std::cin >> temp;

         LNode *node = new LNode(temp);

         head = node;

         curNode = node;

         for (int i = ; i < cnt - ; i++) {

             std::cin >> temp;

             node = new LNode(temp);

             if (!node) {

                 //std::cout << "new Error!" << std::endl;

                 return false;

             }

             curNode->next = node;

             curNode = node;

         }

     }

     return true;

 }

 void LinkList::LListDestory()

 {

     //std::cout << "Destory!" << endl;

     LNode *cur = head;

     if (!cur)

         return;

     LNode *next = cur->next;

     while (cur) {

         delete cur;

         if (next) {

             cur = next;

             next = next->next;

         }

         else

             break;

     }

 }