#include <iostream>
using namespace std;

struct _node{
    int data;
    struct _node *next;
};
typedef struct _node node;

void inputNode(node*, int);
void printNode(node*, int);
node* reverseNodes(node*);

int main(){
    node *head, *ptr;
    head = new node;
// initialize data value
    int n;
    cout << "how many struct do you need: "; cin >> n;
    inputNode(head,n);
    printNode(head,n);

// 插入第一個節點前面:
    node *new_nodeHead;
    new_nodeHead = new node;
    new_nodeHead->next = head;
    head= new_nodeHead;
    cout << "Please input value for inserted node: ";
    cin >> new_nodeHead->data;
    printNode(head,++n);

// 插入最後一個節點前面:
    node *new_nodeTail;
    new_nodeTail = new node;
    // move ptr to the last node
    ptr = head;
    node *last;
    while (ptr != NULL){
        last = ptr;
        ptr = ptr->next;
    }// end while
    new_nodeTail->next = last->next; //new_nodeTail->next = NULL;
    last->next = new_nodeTail;
    cout << "Please input value for inserted node: ";
    cin >> new_nodeTail->data;
    printNode(head,++n);

// 插入第二節點後面:
    node *new_nodeMiddle;
    new_nodeMiddle = new node;
    // move ptr to the last node
    ptr = head;
    node *middle;
    int count = 0;
    while (count < 2){
        middle = ptr;
        ptr = ptr->next;
        count++;
    }// end while
    new_nodeMiddle->next = middle->next; // 精華
    middle->next = new_nodeMiddle;
    cout << "Please input value for inserted node: ";
    cin >> new_nodeMiddle->data;
    printNode(head,++n);

// free memory
    delete new_nodeMiddle;
    delete new_nodeHead;
    delete head;
}




void inputNode(node* ptr, int n){
    int value;
    for (int i = 0; i < n; i++){
        if (i == 0){
            cout << "Please input the value for " << i+1 << " struct: " ;
            cin >> value;
            ptr->data = value;
            continue;
        }

        ptr->next = new node;
        ptr = ptr->next;

        cout << "Please input the value for " << i+1 << " struct: " ;
        cin >> value;
        ptr->data = value;
    }
}

void printNode(node* ptr, int n){
    for (int i = 0; i < n; i++){
        cout << "the value for " << i+1 << " struct: " << ptr->data << endl;
        ptr = ptr->next;
    }
}