“Being on sea, sail; being on land, settle.”
2020.10.04 今天重新整理了数据结构中链表的有关功能及实现，附加完成了带有头节点版本的 反转链表。 LeetCode.206 反转链表: 题目.
所有代码如下： 鉴于可读性的原因，所有变量中的英文单词未采用缩写。
#include <iostream> using namespace std; template<class T> struct Node { T data; //数据域 Node<T>* next; //指针域 Node(){}; Node(T data){this->data = data;}; }; template<class T> class LinkedList { private: Node<T>* firstNode; int listSize; public: LinkedList(int initialCapacity = 10); bool isEmpty() {return listSize == 0;} int size() {return listSize;} T getElement(int index); void erase(int index); void insert(int index, T element); void reverseLinkedList(); void print(); }; template<class T> LinkedList<T>::LinkedList(int initialCapacity) { firstNode = new Node<T>(); firstNode->next = NULL; listSize = initialCapacity; Node<T>* p = firstNode; for(int i = 0; i < initialCapacity; i++) { T element; cout<<"Enter the element :"<<endl; cin >> element; Node<T>* node = new Node<T>(element); p->next = node; p = node; } p->next = NULL; } template<class T> T LinkedList<T>::getElement(int index) {//假定index是从1开始，不包括头节点 if(index < 1 || index > listSize) return -1; Node<T>* p = firstNode->next; for(int i = 1; i <= listSize; i++) { if(i == index) { return p->data; } p = p->next; } return -1; } template<class T> void LinkedList<T>::insert(int index, T element) { Node<T>* p = firstNode->next; Node<T>* targetNode = new Node<T>(element); if(index <= 1) //特殊情况1：头插法 { targetNode->next = firstNode->next; firstNode->next = targetNode; listSize ++; return; } if(index > listSize)//特殊情况2：插在末尾 { for(int i = 1; i < listSize; i++) p = p->next; p->next = targetNode; targetNode->next = NULL; listSize ++; return; } else { for(int i = 1; i < index - 1; i++) p = p->next; targetNode->next = p->next; p->next = targetNode; listSize ++; } } template<class T> void LinkedList<T>::erase(int index) { if(index < 1 || index > listSize) { cout<< "error!" <<endl; } else { Node<T>* p = firstNode; for(int i = 1; i < index; i++) p = p->next; Node<T>* tmp = p->next; p->next = tmp->next; delete tmp; listSize --; } } template<class T> void LinkedList<T>::reverseLinkedList() { Node<T>* currentNode = firstNode->next; Node<T>* previous = currentNode->next; while (previous != NULL) { Node<T>* n = previous->next; previous->next = currentNode; currentNode = previous; previous = n; } firstNode->next = currentNode; } template<class T> void LinkedList<T>::print() { Node<T>* p = firstNode->next; for(int i = 0; i < listSize; i++) { cout<<p->data<<" -> "; p = p->next; } cout<<"NULL"<<endl; cout<<endl; } int main() { LinkedList<int> linkedList(5); cout<<"create a linkedlist:"<<endl; linkedList.print(); cout<<"insert 11 at index -1:"<<endl; linkedList.insert(11, -1); linkedList.print(); cout<<"erase the element of index 6:"<<endl; linkedList.erase(6); linkedList.print(); linkedList.getElement(3); linkedList.isEmpty(); linkedList.size(); cout<<"reverse linkedlist:"<<endl; linkedList.reverseLinkedList(); linkedList.print(); system("pause"); }运行结果如下： 部分功能辅助图： 反转方法链接: 反转链表. （大佬写了三种方法，都写得贼好，我用的属于第三种。）
Over.
