<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> 讯享网
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。链表的入口节点称为链表的头结点也就是head。
1.1链表的类型
单链表：每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），单链表中的指针域只能指向节点的下一个节点。
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。既可以向前查询也可以向后查询。
循环链表：是链表首尾相连。
1.2链表的存储方式
数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
1.3 链表的定义
讯享网
注意：
- 编程语言标准库一般都会提供泛型，即你可以指定 字段为任意类型，而力扣的单链表节点的 字段只有 int 类型。
- 编程语言标准库一般使用的都是双链表而非单链表。单链表节点只有一个 指针，指向下一个节点；而双链表节点有两个指针， 指向前一个节点， 指向下一个节点。
1.4虚拟头结点的创建
使用虚拟头结点的优点
- 简化插入和删除操作：有了虚拟头结点，无论是插入还是删除操作都无需特殊处理链表头节点。
- 统一操作逻辑：避免处理头节点和其他节点时的代码差异，使代码逻辑更加一致。
- 防止空指针异常：当链表为空或只包含一个节点时，虚拟头结点能减少空指针检查。
可以将虚拟头结点定义为一个指针并动态分配内存，或者直接在栈上创建。以下是创建虚拟头结点的几种方法：
1. 使用动态分配的虚拟头结点
动态分配一个空节点，通常将其 设为 0 或不进行初始化（取决于需求）。 指针指向实际的链表头节点。
讯享网
在这种情况下， 本身不保存实际数据，仅作为占位节点。
2. 使用栈上分配的虚拟头结点
可以在栈上创建虚拟头结点，避免动态分配的内存管理。这样虚拟头结点的生命周期会随作用域结束自动释放。
总结：
- 动态分配适合长期使用、需要传递的链表，但需手动管理内存。
- 栈上分配适合局部、短期链表操作，自动管理内存、代码更简洁。
1.5 p1.next和p1->next有什么区别
和 的区别在于 的类型不同：
- 用于对象，直接访问对象的成员。
- 用于指针，通过指针访问所指向对象的成员。
- p1.next：
- 使用点号（）访问成员变量，表示 是一个对象。
- 例如，如果 是 类型的对象，那么 可以访问 的成员变量 。
讯享网
- p1->next：
- 使用箭头（）访问成员变量，表示 是一个指针。
- 如果 是一个指向 类型的指针，那么 可以访问它所指向对象的成员变量 。
203. 移除链表元素(虚拟头结点)
给你一个链表的头节点 和一个整数 ，请你删除链表中所有满足 的节点，并返回新的头节点
示例 1：
讯享网
示例 2：
示例 3：
讯享网
解题代码：
完整ACM模式代码，含链表创建，链表输出打印内容：
讯享网
21. 合并两个有序链表（虚拟头结点）
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
示例 2：
讯享网
示例 3：
讯享网
86. 分隔链表(2个链表然后合并)
给你一个链表的头节点 和一个特定值 ，请你对链表进行分隔，使得所有 小于 的节点都出现在 大于或等于 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
示例 2：
讯享网
23. 合并 K 个升序链表(最小堆)
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
讯享网
示例 2：
示例 3：
讯享网
19. 删除链表的倒数第 N 个结点(快指针先走k后，慢指针走)
给你一个链表，删除链表的倒数第 个结点，并且返回链表的头结点。
示例 1：
讯享网
示例 2：
示例 3：
讯享网
876. 链表的中间结点(快慢指针差2倍)
给你单链表的头结点 ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
讯享网
示例 2：
讯享网
（这道题是我第一次实习面试时候，面试官直接让我写完整实现程序，也就是ACM模式，当时一点也不熟悉，甚至在本地编辑器都不会写ListNode的创建，愣是反应半天没写出来，现在我把完整代码附在下面）
142. 环形链表 II(快慢指针差两倍)
给定一个链表的头节点 ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 是 ，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
讯享网
160. 相交链表(计算长度差后先后走)
给你两个单链表的头节点 和 ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 。
示例 1：
示例 2：
讯享网
示例 3：
讯享网
206. 反转链表()
给你单链表的头节点 ，请你反转链表，并返回反转后的链表。
示例 1：
示例 2：
讯享网
示例 3：
讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/186830.html