先学习一下前置知识：关于链表，你该了解这些！

分享一位群内大佬的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 层。