#include "stdio.h"
#include <iostream>
using namespace std;

template <class T>
struct node {
 T val;
 node* pNext;
};

template <class T>
node<T>* create(T valueFisrt) {
 node<T>* nodeFirst;
 nodeFirst = new node<T>();
 nodeFirst->val = valueFisrt;
 nodeFirst->pNext = NULL;

 return nodeFirst;
}

template <class T>
void printTrace(node<T>* listLink) {
 node<T>* nodeTmp = listLink;
 while (nodeTmp != NULL) {
  cout << nodeTmp->val << " ";
  nodeTmp = nodeTmp->pNext;
 }
 cout << endl;
}

template <class T>
void insertFirst(node<T>*& listLink, const T& value) {
 node<T>* nodeNew = new node<T>;
 if (nodeNew != NULL) {
  nodeNew->val = value;
  nodeNew->pNext = listLink;
  listLink = nodeNew;
 }
}

template <class T>
void insertLast(node<T>* listLink, const T& value) {
 if (listLink == NULL)
  return;

 node<T>* nodeNew = new node<T>;
 if (nodeNew != NULL) {
  nodeNew->val = value;
  nodeNew->pNext = NULL;
  node<T>* nodeTmp = listLink;

  while (nodeTmp->pNext != NULL) {
   nodeTmp = nodeTmp->pNext;
  }
  nodeTmp->pNext = nodeNew;
 }
}

template <class T>
void insertMiddle(node<T>* listLink, T match, T value) {

}

template <class T>
struct node2 {
 T val;
 node2* pNext;
 node2* pLast;
};

template <class T>
node2<T>* create2(T valueFisrt) {
 node2<T>* nodeFirst;
 nodeFirst = new node2<T>();
 nodeFirst->val = valueFisrt;
 nodeFirst->pNext = NULL;
 nodeFirst->pLast = NULL;

 return nodeFirst;
}

template <class T>
void printTrace(node2<T>* listLink) {
 node2<T>* nodeTmp = listLink;
 while (nodeTmp != NULL) {
  cout << nodeTmp->val << " ";
  nodeTmp = nodeTmp->pNext;
 }
 cout << endl;
}

template <class T>
void insertFirst(node2<T>*& listLink, const T& value) {
 node2<T>* nodeNew = new node2<T>;
 if (nodeNew != NULL) {
  nodeNew->val = value;
  nodeNew->pNext = listLink;
  nodeNew->pLast = NULL;
  listLink->pLast = nodeNew;
  listLink = nodeNew;
 }
}

template <class T>
void insertLast(node2<T>* listLink, const T& value) {
 if (listLink == NULL)
  return;

 node2<T>* nodeNew = new node2<T>;
 if (nodeNew != NULL) {
  nodeNew->val = value;
  nodeNew->pNext = NULL;
  node2<T>* nodeTmp = listLink;

  while (nodeTmp->pNext != NULL) {
   nodeTmp = nodeTmp->pNext;
  }
  nodeTmp->pNext = nodeNew;
  nodeNew->pLast = nodeTmp;
 }
}

template <class T>
struct node3 {
 T val;
 node3* pNext;
};

template <class T>
node3<T>* create3(T valueFisrt) {
 node3<T>* nodeFirst;
 nodeFirst = new node3<T>();
 nodeFirst->val = valueFisrt;
 nodeFirst->pNext = nodeFirst;

 return nodeFirst;
}

template <class T>
void printTrace(node3<T>* listLink) {
 if (listLink == NULL)
  return;

 node3<T>* nodeTmp = listLink;
 do {
  cout << nodeTmp->val << " ";
  nodeTmp = nodeTmp->pNext;
 } while (nodeTmp->pNext != listLink);

 cout << endl;
}

template <class T>
void insertFirst(node3<T>*& listLink, const T& value) {
 node3<T>* nodeNew = new node3<T>;
 if (nodeNew != NULL) {
  nodeNew->val = value;
  nodeNew->pNext = listLink;
  listLink = nodeNew;
 }
 // Sai, phai cap nhap lai ca pNext cua bien cuoi cung!.
}

template <class T>
void insertLast(node3<T>* listLink, const T& value) {
 if (listLink == NULL)
  return;

 node3<T>* nodeNew = new node3<T>;
 if (nodeNew != NULL) {
  nodeNew->val = value;
  nodeNew->pNext = listLink;
  node3<T>* nodeTmp = listLink;

  while (nodeTmp->pNext != listLink) {
   nodeTmp = nodeTmp->pNext;
  }
  nodeTmp->pNext = nodeNew;
 }
}

int main(int argc, char *argv[]) {
 node3<int>* listLink2 = create3(1);
 insertLast(listLink2, 2);
 insertLast(listLink2, 3);
 insertLast(listLink2, 4);
 insertFirst(listLink2, 5);
 printTrace(listLink2);

 return 0;
}