链表算法专题（建议收藏）
概念
单链表与双链表的区别
1、遍历和查找方面
时间复杂度均为O(n),但单链表只能单向遍历，双链表能双向遍历
2、向某个节点前后位置插入新元素/删除链表中某个节点
虽然时间复杂度均为O(n)，但单链表如果要插入或删除某个节点targetNode的话,除了要获取这个节点本身外还需要获取该节点的前置节点，然后才能删除，流程是
- 遍历链表，获取待删除节点targetNode的前置节点preNode
- preNode.next = targetNode.next
- targetNode.next = null;
- 删除过程完成，targetNode在后面GC过程中被回收
如果是而双链表只要获取到需要被删除的那个节点即可完成删除，可以省去遍历获取preNode的过程
- 通过targetNode的prev指针获取到它的前置节点preNode
- preNode.next = targetNode.next
- targetNode.next.pre = preNode;
- targetNode.pre = null;
- targetNode.next = null;
- 删除过程完成，targetNode在后面GC过程中被回收
3、反转链表
单链表需要三个辅助指针，双链表只需要两个辅助指针即可， 参考案例
链表哨兵节点
哨兵节点也叫 虚拟头节点，是一种特殊的链表实现技巧，它是一个在逻辑上“无数据意义”的节点，主要是用来简化链表相关操作的代码开发工作
- 有了哨兵节点，那么链表就不存在为空的情况，做链表删除和插入操作的时候，省去判断头结点是否为空的步骤，简化代码
- 使用哨兵节点节点的next始终执行链表头结点，pre节点始终执行尾结点，效果相当于省去了两个用来指向链表头尾节点的两个指针head和tail，简化开发
// 哑结点初始化代码,通过是在构造方法中完成这一步
Node dummy = new Node(0)
dump.next = dump;
dump.pre = dump;
// 哑结点尾插法插入节点代码
public void insertTail(Node node) {
dump.pre.next = node;
node.next = dump;
node.pre = dump.pre;
dump.pre= node;
}
// 哑结点头插法插入节点代码
public void insertHead(Node node) {
node.next = dump.next;
dump.next.pre = node;
dump.next = node;
node.pre = dump;
}
双链表节点与二叉树节点的关联
二叉树节点和双向链表节点在物理结构是完全一样的，它们都包含一个“当前数据以及两个指针部分，但在逻辑结构和用途上存在显著差异。
- 二叉树节点：数据域 + 左子节点指针（left） + 右子节点指针（right），构成的是树形结构，用于表达层级关系，比如文件系统、搜索树、堆等。
- 双向链表节点：数据域 + 前驱指针（prev） + 后继指针（next），构成的是线性结构，表达线性关系，每个节点前后各有一个节点，用于实现线性数据的高效插入和删除，比如LRU缓存、线性表等。
某些场景下可以将二叉树和链表可以互相转换
某些场景下可以将二叉树和链表可以互相结合
哑节点的作用
双链表头尾哑结点
头尾哑节点相当于会分配额外的空间存储这两个哑结点，如果不使用哑结点的话，那只能是在插入的时候初始化头尾节点，这样在编码上会存在一些复杂性，比如删除尾结点的时候需要判断tail是否等于head，即需要考虑只有一个节点的情况，删除普通节点的时候就更麻烦了，需要单独判断这个普通节点是否头节点，是否尾结点，是否链表当前只有这个一个节点，总计要额外考虑三种特殊情况，参考LRU缓存设计，而使用了哑节点，就能保证所有非哑节点的prev和next指针均不为null，简化删除和添加节点的代码逻辑
双循环链表单哑结点
只需要一个哨兵节点，通过这个哨兵节点的next和prev指针即可快速获取链表真正的头节点和尾节点，同时这种结构还保证了每个节点的next和prev指针均不为null，大大简化了添加和删除节点的代码逻辑
环状链表
约瑟夫环问题
双循环链表单哑结点
介绍如上
闭合为环完成链表旋转
循环队列
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值
LRU缓存
LFU缓存
解题思路
递归解题
普通递归
递归 + 集合
多指针解题
pre-cur-next三指针解题法
链表反转
注意，如果是双向链表的话，那么只需要cur-next两个指针即可
快慢指针
普通指针/迭代
栈辅助
链表辅助
哈希辅助
堆辅助
环装链表法
深度优先遍历
思路组合
获取链表中间节点 + 链表反转 + 合并链表
重排链表
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
9
0- 0
已为社区贡献5条内容
所有评论(0)