链表理论基础

链表的类型

单链表

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链表的入口节点称为链表的头结点也就是head。
如图所示：
单链表

双链表

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表既可以向前查询也可以向后查询。
如图所示：

循环链表

循环链表，就是链表首尾相连。
循环链表可以用来解决约瑟夫环问题。

链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
如图所示：
链表的存储方式
这个链表起始节点为2，终止节点为7，各个节点分布在内存的不同地址空间上，通过指针串联在一起。

链表的定义

手写链表

// 单链表
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;}
}

链表的操作

删除节点

删除D节点，如图所示：
删除节点
这里只需要将C节点的next指针指向E节点就可以了。
Java、Python有自己的内存回收机制，不用自己手动释放这个D节点内存。

添加节点

添加F节点，如图所示：
添加节点
可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。
但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

性能分析

链表的特性和数组的特性进行一个对比，如图所示：
性能分析
数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。

leetcode203. 移除链表元素

这题没按照随想录的做法来实现，一开始不知道怎么在本地IDE上创建链表，然后问了下ChatGPT就知道怎么创建链表并赋值的，下面有我IDE的代码。
注意点：

构造并赋值一个单链表/双链表，这需要熟记于心；
遍历链表每个节点前，需要弄清楚所有特殊情况，提前做好特判操作（排除空链表、头结点值为val等特殊情况）；
遍历链表时，比较的是当前节点的下一个节点的值（cur.next.val），类似于指针，目的是便于进行删除或添加的操作；

// 构造一个单链表
class ListNode {// 节点的值int val;// 下一个节点ListNode next;// 节点的构造函数(1个参数)public ListNode(int val) {this.val = val;this.next = null;}
}public class leetcode203 {public static ListNode removeElements(ListNode head, int val) {// 特判:如果头节点的值等于待删除的值，则直接跳到下一个节点while (head != null && head.val == val) {head = head.next;}// 特判:如果头节点的值为空(即待遍历的链表为空链表)，则直接返回nullif (head == null) {return null;}// 然后再从头开始遍历，每次判断下一个节点的值是否与待删除值相等ListNode cur = head;while (cur != null && cur.next != null) {if (cur.next.val == val) {cur.next = cur.next.next;} else {cur = cur.next;}}return head;}// 在main方法里调用public static void main(String[] args) {// 定义题目示例的链表 head//int[] nums = {1,2,6,3,4,5,6};//int[] nums = {};int[] nums = {6,6,6,6};ListNode head = new ListNode(nums[0]);ListNode cur = head;for (int i = 1; i < nums.length; i++) {cur.next = new ListNode(nums[i]);cur = cur.next;}int val = 6;// 调用函数head = removeElements(head, val);// 输出链表cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}}
}

用python二刷，原本在本地IDE上写的，ACM模式，但是报错了，不知道如何解决，就在力扣上写了
递归法：

class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:# 创建虚拟头部节点以简化删除过程dummy_head = ListNode()dummy_head.next = head# 遍历列表并删除值为val的节点cur = dummy_headwhile cur.next:if cur.next.val == val:cur.next = cur.next.nextelse:cur = cur.nextreturn dummy_head.next

leetcode707. 设计链表

这题做得蛮久的，主要在于深入理解链表的各种基础操作，也就是设计链表的五个接口：

int get(int index)：获取链表第 index 个节点的数值
void addAtHead(int val)：在链表的最前面插入一个节点
void addAtTail(int val)：在链表的最后面插入一个节点
void addAtIndex(int index, int val)：在链表第index个节点前面插入一个节点
void deleteAtIndex(int index)：删除链表的第index个节点

这里建议一边写代码的时候一边在草稿纸上画图来理解，比如我就在写获取、插入和删除操作的代码那时候画了一个链表的结构图来理解，方便理解怎么找到第index个节点以及其前驱节点。

还有在链表的头节点前画了个虚拟节点dummyHead = 0，可以时刻提醒我一开始构造链表时有个虚拟节点需要注意，并方便我在写插入操作的代码时能很好地理解如何在头节点前添加一个节点，形成新头节点；还在尾节点后画了个null“节点”，表示尾节点指向null“节点”，以便我在写插入操作的代码时能很好地理解如何在尾节点后添加一个节点，形成新尾节点。

注意点：

初始化链表的操作也要熟悉；size, head
虚拟头节点，时刻注意；
写一个接口时可以调用别的接口（比如addAtHead和addAtTail接口里调用了addAtIndex接口），能提高代码复用性，降低代码冗余；
前驱节点pre，插入和删除操作都要用到；
边写代码边画图，事半功倍。

// 单链表
class ListNode {int val;ListNode next;ListNode(int val) {this.val = val;this.next = null;}
}class MyLinkedList {// 定义存储链表元素的个数int size;// 定义虚拟头结点(名字不重要，dummyHead或者head都行)ListNode head;// 初始化链表public MyLinkedList() {size = 0;head = new ListNode(0);}// 获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点public int get(int index) {// 如果 index 非法，返回 -1if (index < 0 || index >= size) {return -1;}ListNode cur = head;// 因为包含一个虚拟头节点head，所以是要查找第 index+1 个节点for (int i = 0; i <= index; i++) {cur = cur.next;}return cur.val;}// 在链表最前面插入一个节点，等价于在第0个元素前添加public void addAtHead(int val) {addAtIndex(0, val);}// 在链表最后面插入一个节点，等价于在(末尾+1)个元素前添加public void addAtTail(int val) {addAtIndex(size, val);}// 在第 index 个节点之前插入一个新节点// 如果 index 为 0，则说明新插入的节点为链表的新头节点// 如果 index 为链表的长度 size，则说明新插入的节点为链表的新尾结点public void addAtIndex(int index, int val) {// 如果 index 大于链表的长度，则返回空if (index > size) {return;}// 如果 index 小于 0，等同于在头部插入节点(先将index赋值为0)if (index < 0) {index = 0;}// 此时确定要插入一个节点了，链表长度先自增一个单位size++;// 找到要插入节点的前驱节点(记得有个虚拟头结点)ListNode pre = head;for (int i = 0; i < index; i++) {pre = pre.next;}// 插入操作：先让插入节点指向前驱节点的下一个节点，再让前驱节点指向插入节点ListNode toAdd = new ListNode(val);toAdd.next = pre.next;pre.next = toAdd;}// 删除第 index 个节点public void deleteAtIndex(int index) {// 如果 index 小于 0 或者大于等于链表的长度，则直接返回if (index < 0 || index >= size) {return;}// 此时确定要删除一个节点了，链表长度先自减一个单位size--;// 找到要插入节点的前驱节点(记得有个虚拟头结点)ListNode pre = head;for (int i = 0; i < index; i++) {pre = pre.next;}// 删除操作pre.next = pre.next.next;}
}

leetcode206. 反转链表

这题也是思路一下就有，但不知道具体如何实现，还是写代码少了，应该每天都写算法题的，前段时间由于实验室科研项目导致一直没看算法题。

注意点：
1.首先应该申请节点：pre(初始化为null) 和 cur(指向头结点)，以及临时变量 tmp(保存cur.next)；
2. 循环逻辑要弄清晰，最好在一旁画个草稿图帮助自己理解，运行一两个循环试试看；
3. 最后的循环结束条件以及返回值也要弄清楚，建议画图理解；
4. 个人感觉循环中的操作过程类似于数组中的交换元素，可以做类比学习。

class Solution {// 双指针法public ListNode reverseList(ListNode head) {// 申请节点: pre 和 cur, pre 指向 nullListNode pre = null;ListNode cur = head;ListNode tmp = null;// 循环遍历while (cur != null) {// 记录当前节点的下一个节点tmp = cur.next;// 然后将当前节点指向 precur.next = pre;// pre 和 cur 节点都前进一位pre = cur;cur = tmp;}return pre;}
}

递归的两个条件：
终止条件是当前节点或者下一个节点==null
在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句。

递归法中，我们应该关心的主要有三点：
返回值：指向改变的节点，也就是每次递归的最后一个节点
调用单元f(x)做了什么：改变节点head的指向(调用单元f(x)：head.next 指向 head，也就是最后一个节点cur指向其前一个节点head)
终止条件：head 为空指针或者 head.next 为空指针，也就是当前为空或者下一个节点为空；

class Solution {public ListNode reverseList(ListNode head) {// 递归终止条件: 当前为空，或者下一个节点为空if (head == null || head.next == null) {return head;}// 进行递归(cur是返回值：指向改变的节点)ListNode cur = reverseList(head.next);// 这里进行节点指向改变(调用单元f(x)：head.next 指向 head，也就是最后一个节点cur指向其前一个节点head)head.next.next = head;// 防止链表循环，需要将head.next设置为空head.next = null;// 返回节点(每层递归函数都返回cur，也就是最后一个节点)return cur;}
}

用python二刷，在本地IDE上写，ACM模式
递归法：

# Definition for a single linked list
class ListNode:def __init__(self, val, next=None):self.val = valself.next = next# 构建单链表(利用递归)
def build_linked_list(arr):if not arr:return Nonehead = ListNode(arr[0])head.next = build_linked_list(arr[1:])return head#
nums = [1,2,3,4,5]
head = build_linked_list(nums)def reverseList(head: ListNode) -> ListNode:# 递归终止条件是当前为空，或者下一个节点为空if (head == None or head.next == None):return head# 这里的cur就是最后一个节点cur = reverseList(head.next)# 如果链表是 1->2->3->4->5，那么此时的cur就是5# 而head是4，head的下一个是5，下下一个是空# 所以head.next.next 就是5->4head.next.next = head# 防止链表循环，需要将head.next设置为空head.next = None# 每层递归函数都返回cur，也就是最后一个节点return curprint(reverseList(head))