链表
链表是N个数据元素的无限序列，最罕用的是链式表白，也叫线性链表或链表
链表中存储的数据元素也叫节点，一个节点存储的就是一条记录
每个结点的构造包含数据域、指针域两局部
链表拓展
- 单向链表 只能通过上一结点的指针找到下一个结点
- 循环链表 让单向链表最初一个元素的指针指向第一个元素
- 双向链 除了有指向下一个结点的指针外，再减少一个指向上一个结点的指针
- 双向循环链表 同时具备循环链表和双向链表交融的特色
应用场景
一：操作系统内的动态内存调配
二：LRU缓存淘汰算法
罕用操作
// 1.链表插入s.next = p.nextp.next = s// 2.链表删除p.next = p.next.next// 3.链表反转while(curr){ next = curr.next curr.next = prev prev = curr curr = next}// 4 快慢指针// 4.1 奇数个元素链表，快慢指针查问两头结点while(fast && fast.next && fast.next.next){ fast = fast.next.next; slow = slow.next;}// 4.2 快慢指还能够用来判断链表是否有环，如果链表存在环，快指针和慢指针肯定会在环内相遇，即 fast == slow 的状况肯定会产生// 5. 虚构头：链表头可能产生扭转时可应用leetcode
- 141 环形链表
- 142 环形链表Ⅱ
- 202 高兴数
- 206 链表反转
- 91 链表反转Ⅱ
- 25 K 个一组翻转链表
- 61 旋转链表
- 24 两两替换链表中的节点
- 83 删除排序链表中的反复节点
- 82 删除排序链表种的反复元素Ⅱ
- 86 分隔链表
- 138 复制带随机指针的链表