先学习一下前置知识：关于链表，你该了解这些！
分享一位群内大佬的idea刷题指南：分享一个优雅的力扣刷题姿势
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。链表的入口节点称为链表的头结点也就是head。
分类：单链表、双链表、循环链表（顾名思义）。单链表只能单向查询，双链表可以双向查询，循环链表可以解决约瑟夫环问题。
与数组的区别：数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。数组查询复杂度为O(1)，增删复杂度为O(n)；链表相反。
构建函数：参考了刷题指南中的构建方法。
//leetcode.editor.util.ListNode
package leetcode.editor.util;
import java.util.Arrays;
public class ListNode {
public int val;
public ListNode next;
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
ListNode p = this;
while (p != null) {
sb.append(p.val).append(',');
if (p.next == null) {
sb.deleteCharAt(sb.length() - 1);
}
p = p.next;
}
return sb.append(']').toString();
}
/**
* @param s 形如"1,2,3,4,5"的字符串
* @return [1, 2, 3, 4, 5] 的头节点：1
*/
public static ListNode of(String s) {
if ("".equals(s)) return null;
int[] array = Arrays.stream(s.split(",")).mapToInt(Integer::valueOf).toArray();
return of(array);
}
public static ListNode of(int... array){
ListNode _head = new ListNode(), p = _head;
for (int i : array) {
p.next = new ListNode(i);
p = p.next;
}
return _head.next;
}
}
重写了一些方法，添加了一些方法，使得对于链表的各种操作都变得方便。简单的构造形式如下：
//leetcode.editor.util.ListNode
package leetcode.editor.util;
import java.util.Arrays;
public class ListNode {
// 结点的值
int val;
// 下一个结点
ListNode next;
// 节点的构造函数(无参)
public ListNode() {
}
// 节点的构造函数(有一个参数)
public ListNode(int val) {
this.val = val;
}
// 节点的构造函数(有两个参数)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
删除节点：将上一个节点的next指针指向下一个节点。由于Java自带的回收机制，不需要考虑内存释放。
增加节点：上一个节点的next指向新节点，新节点的next指向本节点。
表述方式：删除某节点（不要查询）与删除第几个节点（要查询）。
203.移除链表元素
文章讲解：代码随想录-移除链表元素
视频讲解： 手把手带你学会操作链表
题设：删除链表中等于给定值 val 的所有节点。
难点：对于链表的基础理解。主要是对于头节点的处理。
思路：查找val，删除对应节点。一种方法是删除头节点时head向后移动。另一种方法是创建一个虚拟的头节点。
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
ListNode cur = head;
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
易错点：空链表时，直接返回原头节点。
复杂度分析：
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
707.设计链表
文章讲解：代码随想录-设计链表
视频讲解： 帮你把链表操作学个通透！
题设：你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
-
MyLinkedList()初始化MyLinkedList对象。 -
int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。 -
void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。 -
void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。 -
void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。 -
void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
难点：一道题包含所有链表的基本操作。
//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;
}
易错点：初始需要头节点+链表长度，注意定义细节；头部插入节点时的设置顺序；插入后size要增加。
总结：这道题相当综合，一刷时折磨了自己很久也没debug出来。先把标准答案看会，双向链表有空再说。
206.反转链表
文章讲解：代码随想录-反转链表
视频讲解： 帮你拿下反转链表
题设：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
难点：递归算法的实现。
思路：先用双指针实现，再对照着双指针用递归。画图非常有助于理解，强烈建议先在草稿纸上画一下。
1.双指针法：
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
复杂度分析：
- 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
- 空间复杂度：O(1)。
2.递归法：
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
public ListNode reverse(ListNode pre, ListNode cur) {
if (cur == null) return pre;
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
return reverse(pre, cur);
}
复杂度分析：
时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
