#include <iostream>
using namespace std;

typedef struct Node_st{
    int data;
    Node_st *next;
}Node;
//only for the first node 
void initNode(Node *head, int n){
    head->data = n;
    head->next = NULL;
}
//在结尾添加, 需要遍历到最后一个
void addNode(Node *head, int n){
    Node *newNode = new Node;
    newNode->data = n;
    newNode->next = NULL;
    Node *cur = head;
    while(cur){
        if(cur->next == NULL){
            cur->next = newNode;
            return;
        }
        cur = cur->next;
    }
}
//insertFront
void insertFront(Node **head, int n){
    Node *newNode = new Node;
    newNode->data = n;
    newNode->next = *head;
    *head = newNode;
}
//search
Node *searchNode(Node *head, int n){
    Node *cur = head;
    while(cur){
        if(cur->data == n)
            return cur;
        cur = cur->next;
    }
    cout << "Can not find node " << n << " in the list " << endl;
}
//delete
bool deleteNode(Node **head, Node *ptrDel){
    Node *cur = *head;
    if(ptrDel == *head){
        *head = cur->next;
        delete ptrDel;
        return true;
    }
    while(cur){
        if(cur->next == ptrDel){
            cur->next = ptrDel->next;
            delete ptrDel;
            return true;
        }
        cur = cur->next;
    }
    return false;
}
//copy a list
void copyList(Node *node, Node **pNew){
    if(node != NULL){
        *pNew = new Node;
        (*pNew)->data = node->data;
        (*pNew)->next = NULL;
        copyList(node->next, &((*pNew)->next));
    }
}
//比较两个链表是否一样
bool compareList(Node *node1, Node *node2){
    bool flag;
    if(node1 == NULL && node2 == NULL)
        flag = true;
    else{
        if(node1 == NULL || node2 == NULL)
            flag = false;
        else if(node1->data != node2->data)
            flag = false;
        else
            compareList(node1->next, node2->next);
    }
}
//delete the linklist
void deleteList(Node **node){
   Node *tempNode;
   while(*node){
       tempNode = *node;
       *node = tempNode->next;
       delete tempNode;
   }
}
//display
void display(Node *head){
    Node *list = head;
    while(list){
        cout << list->data << " ";
        list = list->next;
    }
    cout << endl;
}
//test
//if __name__ == '__main__'
int main(){
    Node *newHead;
    Node *head = new Node;

    initNode(head, 111);
    display(head);
    
    addNode(head, 22);
    display(head);

    addNode(head, 333);
    display(head);

    addNode(head, 555);
    display(head);

    addNode(head, 777);
    display(head);

    insertFront(&head, 1024);
    display(head);

    int numDel = 22;
    Node *searcNum = searchNode(head, numDel);
    if(deleteNode(&head, searcNum))
        cout << "Node " << numDel << " deleted !" << endl;
    display(head);

    cout << "the list is copied: " << endl;
    copyList(head, &newHead);
    display(newHead);

    cout << "comparing the two lists" << endl;
    cout << "Are the two lists the same ? " << endl;
    if(compareList(head, newHead))
        cout << "yes, they are the same " << endl;
    else
        cout << "No, not the same." << endl;

    numDel = 333;
    searcNum = searchNode(newHead, numDel);
    if(deleteNode(&newHead, searcNum)){
        cout << " node " << numDel << "is deleted in newHead" << endl;
        cout << "the newHead after deleted is " << endl;
        display(newHead);
    }
    cout << "comparing the two lists" << endl;
    cout << "Are the two lists the same ? " << endl;
    if(compareList(head, newHead))
        cout << "yes, they are the same " << endl;
    else
        cout << "No, not the same." << endl;

    cout << endl;
    deleteList(&newHead);
    display(head);
    deleteList(&head);
    return 0;
}