一、链表理论基础
学习：
1. 链表定义
线性表的一种存储方式，在逻辑上连续的数据在物理存储中可以不连续。
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
this.next = null;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
2. 链表特征
- 数据量不固定
- 易于增删，不便于查询
3. 链表分类
- 单链表：一个节点只有一个指针域，且只指向下一个节点
- 双链表：一个节点有两个指针域，分别指向下一个节点和上一个节点
- 循环链表：头尾指针相互链接，即尾节点的指针域指向头结点
二、203.移除链表元素
题目链接：
学习前：
思路： 不新增节点/新增节点
- 不新增节点：找到第一个非空且值不等于val的节点，作为新的头结点，然后按题目要求修改head之后的节点，返回head
- 新增节点：新增一个节点作为新的头结点，next值为head，然后按题目要求修改head之后的节点。返回新增节点的next值。
新增节点思路更加简单
时间复杂度：均为O(n)
空间复杂度：均为O(1)
学习后：
- 虚拟头结点：dummy head
- 使用虚拟头结点，使得链表的增删操作变得统一，思路清晰
三、707.设计链表
题目链接：
学习前：
思路：
注意修改next的值，保证链表的不间断
学习后：
- 没有判断参数不合法
- 代码重复
- 在添加虚拟节点并进行删除时，未考虑到删除第一个节点的情况
四、206.反转链表
题目链接：
学习前：
思路：
习惯新增虚拟节点，增加了复杂度
时间复杂度：O(n)
空间复杂度：O(1)
学习后：
- 不使用虚拟结点反而更简单
五、学习总结
- 时间：2.5h
- 对于链表的操作，一般使用虚拟节点能降低操作复杂度，使得操作更加统一，但也有不使用虚拟头结点比较好的场景，如就地链表转置
- 注意对方法中的参数进行合法性校验