1、链表定义：
（1）链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
（2）链表的入口节点称为链表的头结点也就是head。
2、链表类型：
单链表：上面说的就是单链表。
双链表：
单链表中的指针域只能指向节点的下一个节点。
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
循环列表：
循环链表，顾名思义，就是链表首尾相连。
循环链表可以用来解决约瑟夫环问题。
3、数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
1、题目链接：代码随想录
2、文章讲解：代码随想录
3、视频讲解： 手把手带你学会操作链表 | LeetCode：203.移除链表元素_哔哩哔哩_bilibili
4、题目：
题意：删除链表中等于给定值 val 的所有节点。
示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2： 输入：head = [], val = 1 输出：[]
示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]
5、难点：两种方式：
6、遵循点：
class Solution {
// 双指针解法
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length - 1;
// 先将结果数组初始化为nums数组
int newResult[] = new int[nums.length];
int index = nums.length - 1;
while (left <= right) {
// 比较左右两个数的大小，将较大的数放入结果数组，并将指针向前移动
if (nums[left] * nums[left] > nums[right] * nums[right]) {
newResult[index] = nums[left] * nums[left];
left++;
} else {
newResult[index] = nums[right] * nums[right];
right--;
}
index--;
}
return newResult;
}
}1、题目链接：代码随想录
2、文章讲解：代码随想录
3、视频讲解：帮你把链表操作学个通透！LeetCode：707.设计链表_哔哩哔哩_bilibili
4、题目：
在链表类中实现这些功能：
5、注意点：
链表操作的两种方式：
6、知识点：head = new ListNode(0)和head = new ListNode()区别
在Java中，ListNode通常是一个用于表示链表节点的类，具有一个整数值（或其他数据类型）和指向下一个节点的引用。对于以下两种初始化链表头节点的方式：
head = new ListNode(0)
这行代码创建了一个新的ListNode对象，并将其初始值（val）设置为0，同时下一个节点（next）默认被初始化为null。当你需要立即创建一个带有特定值（这里是0）的链表节点时，这种方式非常有用。在处理链表问题时，常常用0或特殊的占位值作为哨兵节点，来简化边界条件的处理。
head = new ListNode()
如果ListNode类没有无参数构造器或者没有显示定义构造器，这将会导致编译错误，因为没有匹配的构造函数可以调用。但如果ListNode类有一个默认的无参构造器，那么这行代码将创建一个新的ListNode对象，其值（val）默认初始化为其类型的默认值（对于int是0，对于引用类型是null），并且next属性同样会被初始化为null。然而，在实际处理链表时，这种形式不常见，除非你确实想创建一个空值节点，并且该节点的值不需要有特殊含义。
总结来说，在处理链表时，head = new ListNode(0)更常见，因为它明确地设置了节点的值，而head = new ListNode()仅在你需要无初始值的新节点时使用，并且类提供了无参构造函数支持这种情况。
// 单链表解法
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
}
class MyLinkedList {
// size存储链表元素的个数
int size;
// 虚拟头结点
ListNode head;
// 初始化链表
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
// 获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
public int get(int index) {
// 如果index非法，返回-1
if (index < 0 || index >= size) {
return -1;
}
ListNode currentNode = head;
// 包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
}
return currentNode.val;
}
// 在链表最前面插入一个节点，等价于在第0个元素前添加
public void addAtHead(int val) {
addAtIndex(0, val);
}
// 在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
public void addAtTail(int val) {
addAtIndex(size, val);
}
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
size++;
// 找到要插入节点的前驱
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pred.next;
pred.next = toAdd;
}
// 删除第index个节点
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
if (index == 0) {
head = head.next;
return;
}
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
pred.next = pred.next.next;
}
}// 双链表解法
class ListNode {
int val;
ListNode next, prev;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
}
class MyLinkedList {
// 记录链表中元素的数量
int size;
// 记录链表的虚拟头结点和尾结点
ListNode head, tail;
public MyLinkedList() {
// 初始化操作
this.size = 0;
this.head = new ListNode(0);
this.tail = new ListNode(0);
// 这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！
head.next = tail;
tail.prev = head;
}
public int get(int index) {
// 判断index是否有效
if (index < 0 || index >= size) {
return -1;
}
ListNode cur = this.head;
// 判断是哪一边遍历时间更短
if (index >= size / 2) {
// tail开始
cur = tail;
for (int i = 0; i < size - index; i++) {
cur = cur.prev;
}
} else {
for (int i = 0; i <= index; i++) {
cur = cur.next;
}
}
return cur.val;
}
public void addAtHead(int val) {
// 等价于在第0个元素前添加
addAtIndex(0, val);
}
public void addAtTail(int val) {
// 等价于在最后一个元素(null)前添加
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
// index大于链表长度
if (index > size) {
return;
}
// index小于0
if (index < 0) {
index = 0;
}
size++;
// 找到前驱
ListNode pre = this.head;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
// 新建结点
ListNode newNode = new ListNode(val);
newNode.next = pre.next;
pre.next.prev = newNode;
newNode.prev = pre;
pre.next = newNode;
}
public void deleteAtIndex(int index) {
// 判断索引是否有效
if (index < 0 || index >= size) {
return;
}
// 删除操作
size--;
ListNode pre = this.head;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
pre.next.next.prev = pre;
pre.next = pre.next.next;
}
}1、题目链接：代码随想录
2、文章讲解：代码随想录
3、视频讲解：帮你拿下反转链表 | LeetCode：206.反转链表 | 双指针法 | 递归法_哔哩哔哩_bilibili
4、题目：
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
5、难点：
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表
6、思路：
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点
class Solution {
public ListNode reverseList(ListNode head) {
// 双指针法
ListNode pre = null;
ListNode cur = head;
ListNode temp = null;
while (cur != null) {
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}