上述最常见的情况称为单链表
发布时间：2025-06-24 17:31:43 作者：北方职教升学中心 阅读量：920
这里的双指针在一次又一次循环中都是cur和pre同时往前移动一个位置来遍历链表（不要忘了临时指针tmp）。node=dummyhead意味着node和dummyhead同时指向了虚拟头结点。也就是被delete后， //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针 //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间 //之前我们的dummyhead只用于虚拟头结点，不用太担心这个问题，所以直接delete dummyhead也没啥毛病 size--; } }//打印链表，可写可不写void printListNode(){ ListNode* cur=dummyhead; while(cur->next!=NULL) { cout<<cur->next->val<<endl; cur=cur->next; }}private:int size;//链表结点个数ListNode* dummyhead;//链表的虚拟头结点};
反转链表
文章讲解
链表4.反转链表
视频讲解
帮你拿下反转链表 | LeetCode：206.反转链表 | 双指针法 | 递归法
现学现练：Leetcode206
题目链接
双指针法（重点掌握）
class Solution {public: ListNode* reverseList(ListNode* head) { ListNode* pre=NULL; ListNode* cur=head; while(cur!=NULL)//循环条件不确定一定要画图模拟一下 { ListNode* tmp=cur->next;//用临时变量记录cur下次移动的位置 cur->next=pre;//改变cur的箭头指向，反转 pre=cur;//移动pre cur=tmp;//移动cur } head=pre; return head; }};代码详解：
1.题目想让你做的事：
2.反转过程
3.时间复杂度：O(n),空间复杂度：O(1)
4.双指针是我们的老朋友了，做这样的例题一定要体会双指针的作用是什么。 //tmp=NULL这一步不加，放入leetcode中也是可以运行的。
也做过了有序数组的平方：两个指针一个在左端一个在右端向中间逼近。cur->next=pre达到反转的效果。
我们做过了数组移除元素：快慢指针。
如果让最后一个结点的指针域指向由NULL变为第一个结点，那就首尾相连，变成循环链表。
飞雷神标记（提醒一下，留给二刷）
移除链表元素
请利用递归的方式解决那道例题（学二叉树的时候好好攻克一下递归）
设计链表
在例题中我们设计的是单链表，那请你再设计一个双链表吧！
反转链表
1.请利用递归的方式解决那道例题（学二叉树的时候好好攻克一下递归）
2.请使用栈解决那道例题。
移除链表元素
文章讲解
链表2.移除链表元素
视频讲解
手把手带你学会操作链表 | LeetCode：203.移除链表元素
现学现练：Leetcode203
题目链接
怎么删除结点
ListNode *tmp=c->next;c->next=c->next->next;delete tmp;代码详解
1.我们删除结点是通过指向前一个结点的指针来操作的。
2.链表的入口结点，也就是第一个结点被称为链表的头结点，也就是head。当初学数据结构学到链表这一章心里想的是这么多代码我要怎么敲哦，光知道原理一到具体实现就懵了。 //delete命令指示释放了tmp指针原本所指的那部分内存， //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。这里的头结点相当于我们大学课堂里的首元结点，这里的虚拟头结点相当于我们大学课堂里的头结点。做完了这道题真的感觉豁然开朗。
也做过了长度最小的子数组的滑动窗口：只往一个方向走不回头，不断调整子序列的起始位置。结点包括指针域和数据域，而指针是指向某个结点的，代表了这个结点的地址。
3.因为有时候头结点的处理方式与其他结点的处理方式不同，比较特殊需要分类讨论，所以在后面我们为了方便对包括头结点的所有结点进行统一处理，会在头结点之前再手动创建一个虚拟头结点dummyhead。
所以很多时候都没有注意到链表的结点是怎么定义的，建议还是要掌握一下。
ListNode* tmp=head;head=head->next;//与其它结点的处理有所不同，因为找不到头结点的上一个结点delete tmp;这个时候又有少数好奇宝宝发问了：我对其他结点使用这种方式怎么不行呢？不用找上一个结点还不爽？
然后就写出了这一坨代码
ListNode* cur=head; while(cur!=NULL) { if(cur->val==val) { ListNode* tmp=cur; cur=cur->next; delete tmp; } else { cur=cur->next; } }
比如我要删除B结点，你按照这种方式干完之后你就会发现，A和C之间的连接断开了，而且你写完这个代码你也会发现不知道怎么return了。
// 单链表struct ListNode { int val; // 节点上存储的元素 ListNode *next; // 指向下一个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数};如果是C语言就不用管这个构造函数了，C++的兄弟们可能会有点疑问：这个构造函数我必须要写吗？写和不写有什么区别呢？
如你所见，自己写的构造函数是可以输入参数的，这也就意味着初始化结点时可以直接输入参数：
ListNode* head = new ListNode(5);但是，如果自己不写构造函数，C++会默认生成一个构造函数，但这个构造函数有一个很大的不同就是它是不可以输入参数的！这就导致你在初始化结点时不可以直接输入参数：
ListNode* head = new ListNode();head->val = 5;6.数组与链表的不同：
7.在做链表题目时，如果人容易晕建议多画画图模拟过程。
而双链表的每个结点就有两个指针域，一个指向下一个结点，一个指向上一个结点。
5.平时在刷Leetcode时，链表的结点都默认已经给我们定义了可以直接用。 //delete命令指示释放了tmp指针原本所指的那部分内存， //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。它的每个结点只有一个指针域，只能指向下一个结点。
8. 在链表中，一定要分清结点和指针的区别。最后一个结点的指针域指向NULL，即为空指针。
其实这个时候会发现做链表题多画画图是有好处的....
3.为了以统一的方式来处理所有结点减少不必要的麻烦，我们构造虚拟头结点dummyhead
ListNode* dummyhead=new ListNode(0);//利用new以及自定义的构造函数来构造虚拟头结点dummyhead->next=head;//虚拟头结点的下一个结点就是头结点，这一步千万别忘了！使用虚拟头结点的时候要注意return时由于head在移除过程中可能发生了改变，不要直接return head，要先用dummyhead->next赋值给新的head再删除dummyhead，然后return head
直接使用原来的链表，不设置虚拟头结点
//直接使用原来的链表，不设置虚拟头结点class Solution {public: ListNode* removeElements(ListNode* head, int val) { //如果删除头结点 while(head!=NULL && head->val==val) { ListNode* tmp=head; head=head->next;//移动head delete tmp; } //如果删除的不是头结点 ListNode* cur=head; while(cur!=NULL&&cur->next!=NULL) { if(cur->next->val==val) { ListNode* tmp=cur->next; cur->next=cur->next->next; delete tmp; } else { cur=cur->next; } } return head; }};时间复杂度：O(n)
空间复杂度：O(1)
设置虚拟头结点
class Solution {public: ListNode* removeElements(ListNode* head, int val) { //构造虚拟头结点 ListNode* DummyNode=new ListNode(0); DummyNode->next=head; ListNode* cur=DummyNode; while(cur->next!=NULL) { if(cur->next->val==val) { ListNode* tmp =cur->next; cur->next=cur->next->next; delete tmp; } else { cur=cur->next; } } head=DummyNode->next; delete DummyNode; return head; }};时间复杂度：O(n)
空间复杂度：O(1)
设计链表(涵盖了链表的常见操作)
做这道题构建每个函数时一定要多画图以便了解代码运行的背后逻辑！不能手懒
文章讲解
链表3.设计链表
视频讲解
帮你把链表操作学个通透！LeetCode：707.设计链表
现学现练：Leetcode707
题目链接
这道题你要明白一个区别：比如说下标为1的结点和第1个结点有什么不同？所以要好好读题目，注意审题，比如这道题的提示中明确给出了index>=0
定义链表结构体
//定义链表结构体struct ListNode{ int val;//数据域 ListNode* next;//指针域 ListNode(int val):val(val),next(nullptr){}//构造函数};这次leetcode没在注释里帮你定义链表结点结构体了，注意！
初始化链表
//初始化链表 MyLinkedList() { size=0;//结点个数为0，此时还没有头结点 dummyhead=new ListNode(0);//创建虚拟头结点 }获取下标为index的结点的值
//获取下标为index的结点的值 int get(int index) { if(index<0||index>size-1) { return -1; } else { ListNode* cur=dummyhead->next; { while(index--)//将cur往后移动 { cur=cur->next; } return cur->val; } } }头部插入结点
//首部插入结点,这个新插入的结点变成了新的头结点 void addAtHead(int val) { ListNode* newnode=new ListNode(val);//创建要插入的新结点 newnode->next=dummyhead->next; dummyhead->next=newnode;//这两步不可调换 size++; }尾部插入结点
//尾部插入结点 void addAtTail(int val) { ListNode* newnode=new ListNode(val);//已经默认新结点的指针域为NULL ListNode* cur=dummyhead; while(cur->next!=NULL)//先让cur移动到最后一个结点 { cur=cur->next; } cur->next=newnode; size++; }下标为index的结点前插入
//在下标为index的结点前插入新结点//题目说了，如果index等于链表的长度，那么该节点会被追加到链表的末尾 void addAtIndex(int index, int val) { if(index>size||index<0) { return;//函数是void } else { ListNode* newnode=new ListNode(val); ListNode* cur=dummyhead; while(index--) { cur=cur->next; } newnode->next=cur->next; cur->next=newnode; size++; } }删除下标为index的结点
//删除下标为index的结点 void deleteAtIndex(int index) { if(index<0||index>size-1) { return; } else { ListNode* cur=dummyhead; while(index--) { cur=cur->next; } ListNode* tmp=cur->next; cur->next=cur->next->next; delete tmp; tmp=NULL;//野指针 //指针和结点还是要分清楚的。4.与数组在内存中连续分布不同，链表并不是连续分布的，各个结点通过指针串联在一起。比如new ListNode(0)是一个真实存在的结点，而ListNode* dummyhead=new ListNode(0)相当于我通过new创建了一个占有内存空间的虚拟头结点，我让指针dummyhead指向它。
看了一眼下一章是哈希表，当时学了数据结构只会公式做题不会敲代码啊TAT，到时候又要把之前忘记的知识捡起来...但是不能放弃啊！
我是Rikka，一只普通的私宅大学生，谢谢你能看我的博客(ᕑᗢᓫ∗)˒！
