简单手写单链表

//单链表, pHead处无数据 template<typename T> struct Node { T m_ata; Node *pNext; }; template<typename T> Node<T> * CreateOneNode(const T& data = NULL) { Node<T> *p = (Node<T>*)malloc(sizeof(Node<T>)); p->pNext = NULL; p->m_ata = data; return p; } //创建链表 //头插法，pHead处不含数据 template<typename T> Node<T> *HeadCreateNodeList(const int& len = 0) { Node<T> *pHead = CreateOneNode<T>(); for (int i = 0; i < len; ++i) { Node<T> *p = CreateOneNode<T>(); cin >> p->m_ata; p->pNext = pHead->pNext; pHead->pNext = p; } return pHead; } //尾插法，pHead处不含数据 template<typename T> Node<T> *TailCreateNodeList(const int& len = 0) { Node<T> *pHead = CreateOneNode<T>(); Node<T> *pTemp = pHead; for (int i = 0; i < len; ++i) { Node<T> *p = CreateOneNode<T>(); cin >> p->m_ata; pTemp->pNext = p; pTemp = p; } return pHead; } //头插一个数据,pHead处不含数据 template<typename T> void Push_front(Node<T>* &pHead, const T& data) { Node<T> *p = CreateOneNode<T>(data); p->pNext = pHead->pNext; pHead->pNext = p; } //尾插一个数据 template<typename T> void Push_back(Node<T>* pHead, const T& data) { if (pHead == NULL) return; while (pHead->pNext) { pHead = pHead->pNext; } Node<T> *p = CreateOneNode<T>(data); pHead->pNext = p; } //打印链表 template<typename T> void print(Node<T>* pHead) { if (pHead == NULL) return; pHead = pHead->pNext; while (pHead) { cout << pHead->m_ata << ' '; pHead = pHead->pNext; } cout << endl; } //查找数据 template<typename T> bool Find(Node<T> *pHead, const T& data, Node<T>* &pResult) { if (pHead == NULL) return false; while (pHead->pNext) { pHead = pHead->pNext; if (pHead->m_ata == data) { pResult = pHead; return true; } } return false; } //删除整个链表 template<typename T> void Clear(Node<T> *&pHead) { Node<T> * p; while (pHead) { p = pHead; pHead = pHead->pNext; free(p); } pHead = NULL; } //删除某个元素 template<typename T> void Remove(Node<T> *pHead, const T data) { if (pHead == NULL) return; Node<T> * p; while (pHead->pNext) { p = pHead; pHead = pHead->pNext; if (pHead->m_ata == data) { p->pNext = pHead->pNext; free(pHead); break; } } } //链表排序(选择排序) template<typename T> void SelectionSort(Node<T> *pHead) { if (pHead == NULL) return; Node<T> *pSortedTail = pHead; while (pSortedTail->pNext != NULL) { Node<T> *minNode = pSortedTail->pNext; Node<T> *p = pSortedTail->pNext->pNext; while (p != NULL)//找出最小的结点 { if (p->m_ata < minNode->m_ata) minNode = p; p = p->pNext; } swap(minNode->m_ata, pSortedTail->pNext->m_ata); pSortedTail = pSortedTail->pNext; } } //链表反转, pHead无数据 template<typename T> void Reverse(Node<T> *pHead) { if (pHead == NULL) return; Node<T> *pPre = NULL; Node<T> *pCur = pHead->pNext; Node<T> *pNext; while (pCur) { pNext = pCur->pNext; pCur->pNext = pPre; pPre = pCur; pCur = pNext; } pHead->pNext = pPre; } //合并2个已经有序的链表, pHead1和pHead2需要有数据（不能是头结点） template<typename T> Node<T> * Merge(Node<T> *pHead1, Node<T> *pHead2) { if (pHead1 == NULL) return pHead2; if (pHead2 == NULL) return pHead1; Node<T> *pNew = NULL; if (pHead1->m_ata < pHead2->m_ata) { pNew = pHead1; pNew->pNext = Merge<T>(pHead1->pNext, pHead2); } else { pNew = pHead2; pNew->pNext = Merge<T>(pHead1, pHead2->pNext); } return pNew; } //单链表, pHead处无数据 template<typename T> struct