【力扣高频TOP100】由浅入深细讲反转链表(小白也能听懂)
👨💻��大唐coding：个人主页
🎁 个人专栏: 《力扣高频刷题宝典》《SQL刷题记录》
⛵ 既然选择远方，当不负青春，砥砺前行！
目录
引入
一、链表的基础概念
1.1链表是什么
1.2链表的种类
1.3链表的存储方式
二、链表的增删查改
2.1添加节点
2.2删除节点
2.3总结
三、链表实战之反转链表
3.1题目描述
3.2思路
3.3代码示例
3.4类似题目推荐
四、文章结语
引入
大家好，我是大唐，不知道大家在刚上大学的时候初遇链表是否头疼，我还记得我在第一次学习链表的时候，也是被难住了好久，时间一晃好几年过去了，今天借着讲题的部分，再给大家重温一遍链表的基础概念。今天我们来看一道非常经典而且面试高频的题目------力扣TOP100之反转链表。
那么首先第一件事，链表到底是什么，有什么作用呢？
一、链表的基础概念
1.1链表是什么
链表是一种常见的数据结构，我们可以把链表简单理解为一串珠子，其中每颗珠子都代表一个数据元素，而珠子之间的线则代表它们之间的连接关系。
而这种连接关系在链表中是通过指针来实现的，每一个节点由两部分组成，一个是数据域data（用来存放数据），一个是指针域next（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
1.2链表的种类
单链表：这是最简单的链表类型，每个节点只包含一个指向下一个节点的指针。单链表只能从头部开始遍历，不能从尾部开始遍历。如上图所示。
双链表：双链表中的每个节点都包含两个指针，一个指向前一个节点，一个指向后一个节点。因此，双向链表可以从头部或尾部开始遍历。
循环链表：循环链表是一种特殊的链表，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。也就是说，在循环链表中，从一个节点出发，可以沿着指针方向遍历整个链表，最终回到起始节点。
1.3链表的存储方式
链表的存储方式是不连续的，每个节点都包含数据域和指针域两部分，数据域用于存储数据，指针域用于存储下一个节点的地址。因此，链表是由一个个节点组成的，节点之间的连接通过指针来实现。
我们不难想到另外一种结构---数组，数组也是可以用来存储数据增删查改，那么大家知道它和链表的区别在哪里吗？
链表与数组的区别主要有以下几点：
- 存储方式：链表是动态存储的，可以根据需要动态地分配和释放内存空间，而数组是静态存储的，需要预先分配固定大小的内存空间。
- 内存利用率：链表的内存利用率通常比数组高，因为链表中的每个节点只需要存储数据和下一个节点的地址，而数组中的每个元素都需要占用相同大小的内存空间，即使有些元素可能并不需要那么多空间。
- 访问速度：数组的访问速度通常比链表快，因为数组可以通过索引直接访问任意位置的元素，而链表需要从头节点开始逐个遍历才能访问到指定位置的节点。
- 插入和删除操作：链表在插入和删除节点时比较方便，只需要修改相邻节点的指针即可，而数组在插入和删除元素时可能需要移动大量元素，因此效率较低。
这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。
二、链表的增删查改
那么在学习了上面链表的基础概念和定义后，相比大家已经对链表是什么有一定的了解，那么下面我们开始讲重点，也是我们在刷关于链表算法题时必不可少的一点---增删查改
2.1添加节点
我们想要添加节点，比如在C点和D点之间添加一个F点，我们只需要以下几步：
1、C点指针指向F点
2、F点指针指向D点
只需要这两步，即可大功告成，插入成功，恭喜你完成了通过的第一个小章节！
2.2删除节点
跟增加节点上面类似，不过这次只需要一步即可解决！
1、C点指针指向E点，相当于把原来的D点直接隔开了
不过在完成后，如果是C/C++，需要手动释放D点内存，free即可
其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了
2.3总结
可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。
但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。
三、链表实战之反转链表
相信大家在看完前面链表的基础知识和操作后，已经对链表有了一定的了解了，是不是对链表的算法题跃跃欲试呢，那么下面我们就来练练手。
3.1题目描述
反转链表---难度 ⭐⭐⭐
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
3.2思路
如果再定义一个新的链表，就可以实现链表元素的反转来完成本题，但是其实这是对内存空间的浪费。我们在思考一下，如果只改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，是不是也可以实现呢？如下图所示:
之前链表的头节点是元素1， 反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改变next指针的方向。那么接下来看一看是如何反转的呢？
这里借鉴一下别人的动图，如下图所示：
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。代码如下：
3.3代码示例
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur, pre = head, None
while cur:
tmp = cur.next # 暂存后继节点 cur.next
cur.next = pre # 修改 next 引用指向
pre = cur # pre 暂存 cur
cur = tmp # cur 访问下一节点
return pre
3.4类似题目推荐
大家在做完上面这道题后，如果感觉还可以趁热打铁，可以多做几道题，如下：
🌟移除链表元素
🌟合并有序链表
🌟设计链表（medium）
四、文章结语
如果你已经看到这里了并且感觉这篇文章对你学习链表有所帮助，
那么请不要吝啬你的发财的小手给博主狠狠地扣个
👍 点赞💫收藏 ⭐️ 关注！
拜托拜托这个真的很重要！你们的点赞就是博主更新最大的动力！