看着都简单，其实写起来不是这里出毛病，就是那里出毛病，要命的是，每次写法不同，毛病也不同……
写这个博客用来做总结复习，还有就是看看能不能帮到小白学习数据结构，每当我发现自己感觉没什么可总结的，可说的，就写写博客，这样就有话了。
链表（这里只是单链表）的基本功能包括：创建、插入、删除、清理、排序、查找等其他的功能。
这里做一个总体的实现
1.创建一个链表，并实现基本功能：创建、插入、删除、清理、查找。我会在代码里面加上注释，这样的更方便。
#include <iostream> using namespace std; struct node { int data; node *next; }; //创建链表 void createList(node **head, int len) //这里面不用双重指针也可以，只要你不打算改变 //头节点本身，比如没有删除我下面的头节点那部分。 { node *p = *head; for (int i = 0; i < len; ++i) { node *q = new node; q->data = i; p->next = q; p = p->next; //这里这么写比较好理解 p=q感觉怪怪的 } p->next = NULL; //最后一个尾节点的next要为NULL，要不然会出错的，无法遍历 p = (*head)->next; //下面三行用来删除头节点，并把正式的节点设为头节点 delete *head; *head = p; } //插入元素 void insertElem(node **head, int loca, int data) { int count = -1; //用来计数 node *p = *head; if (loca == 0) //在头节点插入处理方式不一样，单独处理 { node *q = new node; q->data = data; q->next = *head; *head = q; return; //插入完直接退出 } while (p != NULL && count < loca - 1) //找到插入的头一个节点 { p = p->next; count++; } if (p == NULL)//这里还不能判断，上一个循环是因为p==NULL还是count<loca-1退出来的 //所以这里再判断下 { return; } node *q = new node; //插入节点 q->data = data; q->next = p->next; p->next = q; } //遍历链表 void throughList(node **head) { node *p = *head; while (p != NULL) //只要p!=NUL就一直走下去 { cout << p->data << " "; p = p->next; } cout << endl; } //删除节点 void deleteElem(node **head, int loca) { int count = -1; //用来计数找到删除头节点的前一个节点 node *p = *head; if (loca == 0) //头节点的删除和其他节点是不同的，这里单独处理 { node *q = p; p = p->next; delete q; q = NULL; *head = p; //这里需要重新将将p设置为头节点 return; } while (p != NULL && count < loca - 1) //找到需要删除的节点的前一个节点 { p = p->next; count++; } if (p == NULL)//这里还不能判断，上一个循环是因为p==NULL还是count<loca-1退出来的 //所以这里再判断下 { return; } node *q = p->next; //删除节点 p->next = q->next; delete q; q = NULL; } //删除整个链表 void deleteAll(node **head)//用一个额外的节点记录头节点的下一个节点，然后不断删除头节点 { node *p = *head; node *q = p; while (p != NULL) { q = q->next; delete p; p = NULL; p = q; } *head = NULL; //这里也一定要为NULL } int main() { node *head = new node; //创建头节点 head->data = -1; head->next = NULL; createList(&head, 5); //创建链表 insertElem(&head, 3, 10); //插入节点 deleteElem(&head, 0); //删除一个节点 //deleteAll(&head); //删除整个链表 throughList(&head); //遍历链表 return 0; }2.除了基本的操作，关于检测链表中的循环也是一个经典的问题。检测到循环，然后计算循环的长度，最后再消除循环。
//接着上面的代码，直接插进去就可以用 //为了方便，我们自己在链表中弄一个循环 //创建一个循环 void createLoop(node **head) { node *p = *head; node *q = *head; while (p->next != NULL) { p = p->next; } for (int i = 0; i < 2; ++i) //随便找一个节点，然后把尾节点指向它 { q = q->next; } p->next = q;//尾节点指向该节点 } //判断循环长度 void judgeLoopLen(node **head, node *flag) { node *p = flag->next; while (p != flag) { p = p->next; length++; } cout << "the length" << length << endl; } //检测循环 //基本思想就是，定义两个临时的指针，指向头节点，其中一个节点每次指向下下个节点，而另一个指向下一 //个节点，如果存在循环，他们就会相遇，不存在就指向NULL，结束。 bool judgeLoop(node **head) { node *p = *head; //node *q = (*head)->next; //这里这样也行，关键是while循环里面的q永远比p在前面多一个就行 node *q = *head; while (q && q->next && q->next->next)//这里需要这样判断 否则不存在环的时候会访问异常 { p = p->next; q = q->next->next; if (p == q) { judgeLoopLen(head, p); return true; } } return false; } //消除循环 //找尾节点，将他的next设为NULL void deleteLoop(node **head) { node *p = *head; node *q = p; for (int i = 0; i < length - 1; ++i) //让q向后一直指，直到次数比循环本身小1，这样最后就 //可以找到循环起始节点的前一个节点，即尾节点，直接将他的next设为NULL，就消除循环了 { q = q->next; } while (p != q->next) //while(p->next!=q->next) //不行，不能这么判断 { p = p->next; q = q->next; } q->next = NULL; }3.判断链表中的数据是否是回文
//这个很好理解，检查是否有回文用一个栈，放进去，再每个比较一下 bool checkHuiwen(node **head) { stack<int> s; node *p = *head; while (p != NULL) { s.push(p->data); p = p->next; } while (p != NULL) { if (p->data != s.top()) { return false; } p = p->next; s.pop(); } return true; }感觉基本的主要的操作就这些了，外加一个单链表的快排，这道题我能说其实没那么好写吗……我写完了没怎么好好测试，有可能有错的地方，但这个思路肯定没问题。
//单链表的快速排序 void swap1(node *p, node *q) { int temp = p->data; p->data = q->data; q->data = temp; } node* sort(node *low, node *high) { node *p = low; node *q = low; int temp = low->data; while (q->next != high->next) { if (q->data <= temp) { swap1(p, q); p = p->next; } q = q->next; } if (low->next == p) { return low; } if (p == high) { swap1(low, p); return p; } q = low; while (q->next != p && q != NULL) { q = q->next; } swap1(low, p); return p; } void quickSort(node *low, node *high) { node *pation = sort(low, high); node *k = low; if (low != high) { if (low != pation) { while (k->next != pation) { k = k->next; } quickSort(low, k); } if (high != pation) { quickSort(pation->next, high); } } }只需要处理对于中轴在头部和尾部的这两种额外情况就可以了，对于数组来说，他们直接可以用大于等于或者小于等于来判断临界条件，但链表里只能用等于或者不等于，所以需要这两个临界条件的判断。关于基本的快速排序有兴趣的可以看看我这篇文章https://blog.csdn.net/OtherShoreFlower/article/details/97312540
