行业知识
C++ 链表
���录
链表结构
一，单链表
1.实现基本的增删查改
2.对链表进行一些操作
（1）删除等于给定值的所有节点。
（2）翻转链表
（3） 返回中间节点的地址
（4）倒数第k个节点
（5）合并有序链表
（6）分割链表
（7）链表回文
（8）链表相交
（9）环形链表
二，双向链表
1.增删查改
虽然C++中有list容器，但是在某些oj题中会出现有关链表的题，所以写一篇C++链表。
省去太过官方的定义，只做最简单易懂的介绍。
链表结构
一个数据所在的内存块被分为两个部分，第一个部分放数据，而第二个部分则放下一个数据的地址，以此来连接各个数据，最后一个内存块放的地址为NULL。这样的一个内存块叫做节点。
在代码中，链表的一个节点是这样的：
struct ListNode{int data;ListNode* next;//结构体指针}; 链表有一定的缺陷：每存放一个数据都需要伴随下一个数据的地址并且不支持随机访问。
一，单链表
先来看最简单的单链表。
1.实现基本的增删查改
#include#include#includeusing namespace std;struct ListNode{int data;ListNode* next;//结构体指针};void Listprintf(ListNode* phead){ListNode* cur=phead;while (cur != NULL){cout data next;}}void Listpushback(ListNode** pphead, int x){ListNode* newnode = new ListNode{ x,NULL };if (*pphead == NULL){*pphead = newnode;}else{ListNode* tail= *pphead;while(tail->next != NULL){tail = tail->next;}tail->next = newnode;}}void test_1(){ListNode* phead = NULL;Listpushback(&phead, 1);Listpushback(&phead, 2);Listpushback(&phead, 3); Listprintf(phead);}int main(){test_1();return 0;} 运行结果：
在这段代码中有一些需要注意的地方，比如：
在Listpushback这个函数中，参数是二级指针，如果写成一级指针：
void Listpushback(ListNode* pphead, int x){ListNode* newnode = new ListNode{ x,NULL };if (pphead == NULL){pphead = newnode;}else{ListNode* tail= pphead;while(tail->next != NULL){tail = tail->next;}tail->next = newnode;}} 则结果会变成：
没有任何输出。
原因是原本的指针phead是没有任何指向的，这个指针没有指向某一个地址，而是一个空指针，在函数传参的时候，如果参数pphead是一级指针，则pphead也是空指针，改变pphead，并不会影响到phead，所以最终一通操作下来，phead还是空指针，输出结果也就是空的。
下面再增加一些功能：
#include#include#includeusing namespace std;struct ListNode{int data;ListNode* next;//结构体指针};void Listprintf(ListNode* phead){ListNode* cur=phead;while (cur != NULL){cout data next;}cout next;}tail->next = newnode;}}//头插void Listpushfront(ListNode** pphead, int x){ListNode* newnode = new ListNode{ x,NULL };newnode->next = *pphead;*pphead = newnode;}//尾删void Listpopback(ListNode** pphead){if (*pphead == NULL){return;}if ((*pphead)->next == NULL){delete(*pphead);*pphead = NULL;}else{ListNode* tail = *pphead;ListNode* prev = NULL;while (tail->next){prev = tail;tail = tail->next;}delete(tail);tail = NULL;prev->next = NULL;}}//头删void Listpopfront(ListNode** pphead){if (*pphead == NULL){return;}else{ListNode* newnode = (*pphead)->next;delete(*pphead);*pphead = newnode;}}//查找元素，返回值是地址ListNode* Listfind(ListNode* phead, int x){ListNode* cur = phead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;}//插入元素，在pos的前一个位置插入//配合Listfind使用，具体使用见test_insert函数void Listinsert(ListNode** phead, ListNode* pos, int x){ListNode* newnode = new ListNode{ x,NULL };if (*phead == pos){newnode->next = (*phead);*phead = newnode;}else{ListNode* posprev = *phead;while (posprev->next != pos){posprev = posprev->next;}posprev->next = newnode;newnode->next = pos;}}//单链表并不适合在前一个位置插入，因为运算较麻烦，会损失效率//包括c++中为单链表提供的库函数也只有一个insert_after而没有前一个位置插入//在后一个位置插入相对简单void Listinsert_after(ListNode** phead, ListNode* pos, int x){ListNode* newnode = new ListNode{ x,NULL };newnode->next = pos->next;pos->next = newnode;}//删除指定位置的节点void Listerase(ListNode** pphead, ListNode* pos){if (*pphead == pos){*pphead = pos->next;delete(pos);}else{ListNode* prev = *pphead;while (prev->next!=pos){prev = prev->next;}prev->next = pos->next;delete(pos);}}//释放链表void Listdestory(ListNode** pphead){ListNode* cur = *pphead;while(cur){ListNode* next = cur->next;delete(cur);cur = next;}*pphead = NULL;}void test_insert(){ListNode* phead = NULL;Listpushback(&phead, 1);Listpushback(&phead, 2);Listpushback(&phead, 3);Listprintf(phead);ListNode* pos = Listfind(phead, 2);if (pos != NULL){Listinsert(&phead, pos, 20);}Listprintf(phead);pos = Listfind(phead, 2);if (pos != NULL){Listinsert_after(&phead, pos, 20);}Listprintf(phead);Listdestory(&phead);}void test_find(){ListNode* phead = NULL;Listpushback(&phead, 1);Listpushback(&phead, 2);Listpushback(&phead, 3);Listprintf(phead);ListNode* pos = Listfind(phead, 2);if (pos != NULL){pos->data = 20;//Listfind不仅能查找，也能借此修改，这也是函数返回地址的原因}Listprintf(phead);Listdestory(&phead);}void test_erase(){ListNode* phead = NULL;Listpushback(&phead, 1);Listpushback(&phead, 2);Listpushback(&phead, 3);Listprintf(phead);ListNode* pos = Listfind(phead, 2);if (pos != NULL){Listerase(&phead, pos);}Listprintf(phead);Listdestory(&phead);}void test_pop_and_push(){ListNode* phead = NULL;Listpushback(&phead, 1);Listpushback(&phead, 2);Listpushback(&phead, 3);Listprintf(phead);Listpushfront(&phead, 1);Listpushfront(&phead, 2);Listpushfront(&phead, 3);Listprintf(phead);Listpopback(&phead);Listpopfront(&phead);Listprintf(phead);Listdestory(&phead);}int main(){//test_pop_and_push();test_find();//test_insert();//test_erase();return 0;} test_pop_and_push()测试结果：
test_find()测试结果：
test_insert()测试结果：
test_erase()测试结果：
2.对链表进行一些操作
（1）删除等于给定值的所有节点。
例如：在一条链表中删除值为6的节点。
#include#include#includeusing namespace std;struct ListNode{int data;ListNode* next;//结构体指针};void Listprintf(ListNode* phead){ListNode* cur=phead;while (cur != NULL){cout data next;}cout next;}tail->next = newnode;}}ListNode* creatlist(){ListNode* phead = NULL;Listpushback(&phead, 1);Listpushback(&phead, 9);Listpushback(&phead, 6);Listpushback(&phead, 8);Listpushback(&phead, 6);Listpushback(&phead, 2);Listpushback(&phead, 3);return phead;}ListNode* removeElements(ListNode* head, int x){ListNode* prev = NULL;ListNode* cur = head;while (cur){if (cur->data == x){if (cur == head)//如果第一个元素就是要删除的，进行头删{head = cur->next;delete(cur);cur = head;}else{prev->next = cur->next;delete(cur);cur = prev->next;}}else{prev = cur;cur = cur->next;}}return head;}int main(){ListNode*phead = creatlist();//先创建一条链表Listprintf(phead);phead = removeElements(phead, 6);//删除值为6的节点Listprintf(phead);return 0;} 自测结果：
当然如果是一条全为6的链表也是可以完成删除的：
这里再说一下为什么删除元素和创建链表这两个函数的参数不是二级指针，因为这两个函数是要返回一个指针的。
（2）翻转链表
比如：将1->2->3->4->5翻转为5->4->3->2->1
翻转链表的方式很多，这里只写两种作为参考：
第一种，翻转指针。
这种方法的逻辑是定义三个指针，一个用来纪录当前位置的前一个位置，一个用来纪录当前位置，一个用来纪录当前位置的后一个位置，再通过将当前位置指向下一个位置的指针修改为指向上一个位置，再往后迭代，以达到翻转链表的目的。
为什么要三个指针呢，因为将当前位置指向前一个位置之后，就找不到当前位置的下一个位置了，所以需要第三个指针来指向下一个位置。
代码部分由于只有测试函数不一样，其余代码差异不大，所以仅贴出测试函数部分：
ListNode* reverseList(ListNode* head){if (head == NULL){return NULL;}ListNode* prev, * cur, * next;prev = NULL;cur = head;next = cur->next;while (cur){cur->next = prev;//翻转指针//往后迭代prev = cur;cur = next;if (next)//这里是因为当cur指向最后一个节点的时候，next就已经是NULL了，这个时候如果再执行next=next->next则会出现错误{next = next->next;}}return prev;} 自测结果：
测试结果（测试网站：牛客网）：
第二种方式，创建新链表进行头插
这种方法的逻辑是将原链表中的节点取下来头插到新链表newlist中，同样的，需要三个指针，一个为NULL，即为新链表newlist，一个纪录原链表从头开始的地址，一个纪录下一个位置。将原链表第一个节点取下来对newlist进行头插，再取第二个第三个，往后迭代。
ListNode* reverseList(ListNode* head){ListNode* cur = head;ListNode* newlist = NULL;ListNode* next = NULL;while (cur){next = cur->next;//头插cur->next = newlist;newlist = cur;//往后迭代cur = next;}return newlist;} 自测结果：
测试结果（测试网站：牛客网）：
（3） 返回中间节点的地址
如果有两个中间节点，返回第二个中间节点。
这种操作比较简单，最容易想到的方法就是先遍历一次整个链表找出有几个节点，再遍历一次找出中间节点
但是如果要求只能遍历一次呢，所以这里不采用遍历两次的方法，而采用快慢指针的方式只遍历一次。
逻辑就是定义两个指针，一个走的更慢，一次走一步，另一个走的更快，一次走两步。
ListNode* middleNode(ListNode* head){ListNode* slow, * fast;slow = fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;} 自测结果：
（4）倒数第k个节点
输入一个链表和k，输出从倒数第k个节点到最后一个。
思路和快慢指针相似，定义两个指针，一个指针先走k步。
ListNode* findK(ListNode* head, int k){ListNode* fast, * slow;fast = slow = head;while(k--){if (fast == NULL)//如果当fast等于NULL时k仍不为0，则k大于链表长度{return NULL;}fast = fast->next;}while (fast){fast = fast->next;slow = slow->next;}return slow;} 自测结果：
测试结果（测试网站：牛客网）：
（5）合并有序链表
思路比较简单，依次比较链表中的节点，将较小的节点尾插到新链表。
当然还有一种做法是将一个链表直接插入到另一个链表中，这种方式画图画起来倒是简单，但是实际写起来很麻烦，这里不推荐这种写法，也不会写这种。
ListNode* mergeTwoList(ListNode* l1, ListNode* l2){if (l1 == NULL)//如果一个链表为空，则返回另一个{return l2;}if (l2 == NULL){return l1;}ListNode* head = NULL;ListNode* tail = NULL;while (l1 && l2){if (l1->data data){if (head == NULL){head = tail =l1;}else{tail->next = l1;tail = l1;}l1 = l1->next;}else{if (head == NULL){head = tail = l2;}else{tail->next = l2;tail = l2;}l2 = l2->next;}}if (l1){tail->next = l1;}if(l2){tail->next = l2;}return head;} 自测结果：
我这里是将两条1->2->3->4->5->6的链表合并。
测试结果（测试网站：牛客网）：
可以看到这种不带哨兵位的写法也还是比较麻烦，要判断头为不为空，所以下面再写一种带哨兵位的写法。
带哨兵位（也叫带头）就是我们去给链表多定义一个头结点，这个节点不存储有效数据。
ListNode* mergeTwoList(ListNode* l1, ListNode* l2){if (l1 == NULL)//如果一个链表为空，则返回另一个{return l2;}if (l2 == NULL){return l1;}ListNode* head = NULL, * tail = NULL;head = tail = new ListNode;//哨兵位的头结点while (l1 && l2){if (l1->data data){ tail->next = l1; tail = l1; l1 = l1->next; }else{tail->next = l2;tail = l2;l2 = l2->next;}}if (l1){tail->next = l1;}if (l2){tail->next = l2;}ListNode* list = head->next;delete(head);return list;} 自测结果：
测试结果（测试网站：牛客网）：
（6）分割链表
给定一个值x，将所有小于x的节点排在其余节点之前，且不能改变原来的数据顺序，返回重新排列后的链表头指针。
思路：定义两条链表，一条将小于x的所有节点按照原顺序连接成链表，另一条将大于x的所有节点按照原顺序连接成链表，最后再合起来。
ListNode* partition(ListNode* phead, int x){ListNode* lesshead, * lesstail, * greaterhead, * greatertail;lesshead = lesstail = new ListNode;//定义一个哨兵位头结点，方便尾插lesstail->next = NULL;greaterhead = greatertail = new ListNode;greatertail->next = NULL;ListNode* cur = phead;while (cur){if (cur->data next = cur;lesstail = cur;}else{greatertail->next = cur;greatertail = cur;}cur = cur->next;}lesstail->next = greaterhead->next;greatertail->next = NULL;//举个例子，这样一条链表:1->4->15->5,现在给的x是6，那么排序后15应该在最后，正因如此，重新排序后15的next是没变的，仍然指向5，不手动将next改为NULL，就会成环，无限排下去。ListNode* newhead = lesshead->next;delete(lesshead);delete(greaterhead);return newhead;} 自测结果：
测试结果（测试网站：力扣）：
（7）链表回文
判断链表是否回文。
思路，先找到一条链表的中点，将后半段逆置，设置两个指针，一个从头开始，一个从逆置后的头开始，逐个判断直到最后。
图：
节点奇数个：
节点偶数个：
代码：
ListNode* middleNode(ListNode* head){ListNode* slow, * fast;slow = fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}ListNode* reverseList(ListNode* head){ListNode* cur = head;ListNode* newlist = NULL;ListNode* next = NULL;while (cur){next = cur->next;//头插cur->next = newlist;newlist = cur;//往后迭代cur = next;}return newlist;}bool check(ListNode* head){ListNode* mid = middleNode(head);ListNode* rhead = reverseList(mid);ListNode* curHead = head;ListNode* curRhead = rhead;while(curHead&&curRhead){if (curHead->data != curRhead->data)return false;else{curHead = curHead->next;curRhead = curRhead->next;}}return true;} 自测结果：
测试结果（测试网站：牛客网）：
（8）链表相交
给两个单链表的头结点，找出并返回两个单链表相交的起始节点，没有交点则返回null。
最简单粗暴的思路就是将A链表的每个节点和B链表的每个节点挨着挨着比较，这里不使用这一种。
还有一种思路就是，找到A和B的尾结点对比，如果一样则有交点，如果不一样则没有交点，有交点的情况下又该怎样找到相交的起始节点？
如果两条链表在相交之前的节点个数一样的话，那么找到相交的起始节点就很简单，定义两个指针同时向前走直到相等即可，所以我们在找链表A和B的尾结点的时候，同时纪录下A和B的长度，用长的减去短的得到一个数x，再分别为两条链表定义头指针，让长的那条链表的头指针先走x步，那么就可以当做是在相交之前节点数一样了。
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { if(pHead1==NULL) { return NULL; } if(pHead2==NULL) { return NULL; } ListNode* tail1=pHead1; ListNode* tail2=pHead2; int len1=1,len2=1; while(tail1->next) { len1++; tail1=tail1->next; } while(tail2->next) { len2++; tail2=tail2->next; } if(tail1!=tail2)//不相交 { return NULL; } int gap=abs(len1-len2); ListNode* longlist=pHead1; ListNode* shortlist=pHead2; if(len1next; } while(longlist!=shortlist) { longlist=longlist->next; shortlist=shortlist->next; } return longlist; } 测试结果（测试网站：牛客网）：
（9）环形链表
判断链表是否带环，并且返回环的入口节点。
判断是否带环的思路比较简单，定义两个指针，一个走得快，一次走两步，一个走得慢，一次走一步，如果不带环，那么走得快的最终会走到NULL，如果带环，那么走得快的会和走得慢的相遇。
要找环的入口节点，也需要定义两个指针，一个从链表头开始，一个从快慢指针相遇的位置开始，他们同时出发，当这两个指针相遇时，所在的位置就是入口节点。
这里做简单的证明，假设链表头到入口节点距离是L，快慢指针相遇的位置meetnode距离入口节点为x
假设C是环的长度，当快慢指针相遇时，快指针走的距离是L+N*C+x，N是快指针走的圈数，慢指针走的距离是L+x，因为快指针一次走两步，慢指针一次走一步，所以快指针走的距离是慢指针的两倍，所以有：
L+N*C+x=2（L+x）
得到：
L+x=N*C
L=（N-1）*C+C-x
其中C-x即为meetnode到入口节点的距离，所以当头指针和从meetnode出发的指针相遇时，头指针走了L，从meetnode出发的指针走了C-x，相遇点即为入口节点。
代码：
ListNode* EntryNodeOfLoop(ListNode* pHead) { ListNode*fast=pHead; ListNode*slow=pHead; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(fast==slow) { ListNode*meet=fast; while(meet!=pHead) { meet=meet->next; pHead=pHead->next; } return pHead; } } return NULL; } 测试结果（测试网站：牛客网）：
这里再说下还有另一种处理方式，就是将meetnode作为链表的尾，meetnode的next作为链表的头，就转化成了两条相交链表找第一个相交节点的问题，这种方式写起来会麻烦一些，这里也不做代码实现。
二，双向链表
双向链表的一个数据所在的内存块是被分成了三部分，除了像单链表那样一部分存储数据，一部分存储下一个数据的地址之外，还要有一部分来存储上一个数据的地址。
在代码中如下：
struct ListNode{int data;ListNode* next;//结构体指针ListNode* prev;}; 双向链表的结构：
其中最常用的是双向带头（哨兵位）循环链表
后面的代码中双向链表也都是这种。
1.增删查改
这里多说一句，很多人都会下意识的认为在带哨兵位的链表中，哨兵位是一条链表开始的位置，但是实际上哨兵位的下一位才是。
#include#include#includeusing namespace std;struct ListNode{int data;ListNode* next;//结构体指针ListNode* prev;};ListNode* Initlist()//初始化双向带头（哨兵）循环链表{ListNode* phead=new ListNode;phead->next = phead;phead->prev = phead;//定义一个哨兵位，自己的next和prev指向自己return phead;}void pushback(ListNode* phead,int x)//尾插{ListNode* tail = phead->prev;//循环链表，哨兵位的前一个就是尾ListNode* newhead = new ListNode;newhead->data = x;newhead->next = phead;newhead->prev = tail;tail->next = newhead;phead->prev = newhead;}void popback(ListNode* phead)//尾删{if (phead->next == phead)//链表为空，不能再删了return;ListNode* tail = phead->prev;ListNode* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;delete(tail);}void pushfront(ListNode* phead,int x)//头插{ListNode* next = phead->next;ListNode* newnode = new ListNode;newnode->data = x;phead->next = newnode;newnode->prev = phead;newnode->next = next;next->prev = newnode;}void popfront(ListNode* phead)//头删{if (phead->next == phead)//链表为空，不能再删了return;ListNode* next = phead->next;ListNode* dnext = next->next;phead->next = dnext;dnext->prev = phead;delete(next);}ListNode* listFind(ListNode* phead, int x)//查找{ListNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;}void insertList(ListNode* pos, int x)//指定位置插入{ListNode* prev = pos->prev;ListNode* newnode = new ListNode;newnode->data = x;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}void eraseList(ListNode* pos)//指定位置删除{ListNode* posNext = pos->next;ListNode* posPrev = pos->prev;posNext->prev = posPrev;posPrev->next = posNext;delete(pos);pos = NULL;}void printlist(ListNode* phead){ListNode* cur = phead->next;while (cur != phead){cout data next;}cout next == phead)//链表为空，不能再删了return;eraseList(phead->prev);}void pushfront(ListNode* phead,int x)//头插{insertList(phead->next, x);}void popfront(ListNode* phead)//头删{if (phead->next == phead)//链表为空，不能再删了return;eraseList(phead->next);} 最后再说一下为什么双向链表中的函数的参数是一级指针而不是像之前单链表那样是二级指针的问题 ，这是因为在我写的双向链表中是带了头的，也就是带了哨兵位，所以不需要考虑传进来的是空指针，改变形参不会影响变量的问题，而在我写单链表的时候是没有带头的。
