<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> 讯享网
前置知识：无，会的可以直接跳过。
内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。
链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。
链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。
观察上图，链表的组成单位是节点（node）对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”：
- 链表的首个节点被称为“头节点”，最后一个节点被称为“尾节点”。
- 尾节点指向的是“空”，它在 Java、C++ 和 Python 中分别被记为 、 和 。
- 在 C、C++、Go 和 Rust 等支持指针的语言中，上述“引用”应被替换为“指针”。
如下面代码所示，链表节点 除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。
讯享网
双链表是在上述单链表的基础上，再加一个指向前一个节点的指针，插入和删除操作需要额外再对指向前一个节点的指针进行操作，双链表的数据结构如下所示：
链表的主要操作就两个：插入节点和删除节点。
插入节点
在链表中插入节点非常容易。如下图所示，假设我们想在相邻的两个节点 和 之间插入一个新节点 ，则只需改变两个节点引用（指针）即可，时间复杂度为 。相比之下，在数组中插入元素的时间复杂度为 ，在大数据量下的效率较低。
插入节点的代码示例如下：
讯享网
删除节点
如下图所示，在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。请注意，尽管在删除操作完成后节点 仍然指向 ，但实际上遍历此链表已经无法访问到 ，这意味着 已经不再属于该链表了。
删除节点的代码示例如下：
通过前面的概念理解了链表的基本模型以及链表的操作方式，现在可以实现一个链表。我们可以按照 leetcode707 设计链表进行实现并测试。
单链表的实现
链表节点是默认给出的，与上面描述的是一样的。
讯享网
双链表的实现
双链表的实现无非在单链表的基础上增加一个指针的处理
反转链表
题目描述如下图所示:
思路：反转链表需要修改当前节点的 指针的指向为前一个节点，因此需要记录前一个节点和当前节点，当修改完以后还要往后遍历修改下一个节点，而前面修改当前节点的 指针的指向已经让当前节点与整个链表断开联系，所以需要提前记录当前节点的下一个节点。故分别使用 、 、 表示，其中 和 一开始为空指针， 为参数节点。循环判断当前节点是否为空，若不为空表示需要反转，用 保存下一个节点的地址，然后将当前节点的指针指向 ，再更新 为当前指针表示此节点已完成反转，最后更新 为下一个节点，执行下一个循环，直达循环结束，返回 节点即为整个反转后链表的头结点。
代码示例如下：
讯享网
测试地址：leetcode206 反转链表
合并两个有序链表
题目描述如下图所示:
思路：可以直接在原链表上操作，也可以创建新链表操作，下面使用第二种方式。首先创建一个新链表，然后分别遍历两个旧链表，直到其中一个链表遍历结束则停止遍历，每次遍历都要比较两个链表当前节点的值，将较小的节点添加到新链表中，最后将还有剩余的链表全部添加到新链表中。
代码示例如下：
测试地址：leetcode21 合并两个有序链表
两数相加
题目描述如下图所示:
思路：可以复用老链表，不过下面的实现没有这么做，都是生成的新节点(为了好理解)。创建一个新链表，因为是两数相加，所以需要用一个变量保存进位信息(默认为0)，用一个变量保存求和信息。同时从头结点开始遍历两个链表，只要结点不为空，就将结点的值加到和上，在加上进位信息的值，通过最后的和获取进位信息和值信息，将值信息放到新链表节点中。循环执行，每次都需要将和结果置为 0，最后判断进位信息是否为 1，如果是 1 在新链表中再添加一个值为 1 的节点。
代码示例如下：
讯享网
测试地址：leetcode2 两数相加
划分链表
题目描述如下图所示:
思路：创建两新链表，分别保存小于目标值的节点和大于等于目标值的节点，不打乱顺序，最后将大于等于的那些节点追加到小于部分的链表后面。由于是直接将整个链表添加到新链表中，因此最后的结果可能会是一个环，为了解决这个问题需要在添加到新链表时，将当前节点与原链表解除关系。
代码描述如下：
测试地址：leetcode86 划分链表
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/203160.html