链表
# 基础概念
链表是一种常用的数据结构，它是由一系列节点组成的，每个节点包含两部分：数据域和指针域。数据域存储节点的数据，指针域存储下一个节点的地址。
# 种类
链表可以分为单向链表、双向链表和循环链表三种:
单向链表中，每个节点只包含一个指针域，指向下一个节点
双向链表中，每个节点包含两个指针域，分别指向前一个节点和后一个节点
循环链表中，最后一个节点的指针域指向第一个节点，形成一个环
# 优点
插入和删除元素方便：由于链表节点包含指针域，因此在链表中插入或删除元素只需要修改指针域的指向即可，不需要移动其他元素，因此效率很高。
链表长度可以动态变化：由于链表的内存空间是动态分配的，因此链表长度可以随时增加或减少，不受内存限制。
可以有效利用内存空间：由于链表节点是分散存储在内存中的，因此可以有效利用内存空间，不会造成内存碎片问题。
# 缺点
随机访问效率低：由于链表节点是通过指针连接起来的，因此无法直接通过下标访问元素，需要从头开始遍历整个链表，效率较低。
存储需要额外空间：由于链表节点需要额外的指针域来存储下一个节点的地址，因此相对于数组等静态数据结构，链表存储需要额外的空间。
链表在很多场景中都有广泛的应用，比如实现栈、队列、图等数据结构，以及字符串匹配算法等。
# 做题技巧
# 理解链表的指向
就拿基础的单链表来说，每个节点有一个指向域（指针），指向下一个节点。
这个指针的作用是连接链表中的节点，使得节点之间可以通过指针相互访问和操作。
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针（指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量）
p→next = p→next→next ⇒ 指的是p结点的next 指针存储了p结点的下下结点的内存地址
# 这句话有点绕，可以这样理解这个过程
假设当前链表为 A->B->C，p节点是指向B的指针，p→next 指向B的下一个节点C，p→next→next 指向C的下一个节点(即下下个节点)。
执行上述代码后，相当于将 p 的 next 指针直接指向了下下个节点，即跳过了 B 这个节点，此时链表变为 A->C，B 节点被删除了。
# 指针丢失、指针越界、内存泄露
在链表中，每个节点的指针都是存储在内存中的，因此在使用指针时，需要注意空指针和野指针等安全问题
- 指针丢失
一个指针指向了一个动态分配的内存块，但在后续的程序执行过程中，该指针的值被改变，无法再访问原本指向的内存块
- 指针越界
访问链表中不存在的节点时，比如，访问链表中的第n个节点，但链表只有n-1个节点，这时程序就会试图访问不存在的节点，导致指针越界错误。这种错误通常会导致程序崩溃或异常结束。
- 内存泄露
使用动态内存分配时，没有正确地释放已经分配的内存，导致这部分内存无法再被程序访问到，造成内存浪费和程序的不稳定性
假设我们要在p和b节点中插入x，常见的错误如下：
p->next = x; // 将p的next指针指向x结点；
x->next = p->next; // 将x的结点的next指针指向b结点；
第一步操作后p→next指针已经不再指向结点b，而是指向结点x
第二步代码相当于把x赋值给x→next，也就是自己指向自己，指针丢失了
# 注意事项
插入结点时要注意操作的顺序，先将结点x的next指针指向结点p，再把结点p的next指针指向x
在链表中删除节点时，需要更新前一个节点的next指针，以使其指向被删除节点的下一个节点。如果没有更新指针，就会导致链表出现错误的指针引用，甚至出现内存泄漏
在使用指针前将其初始化为空指针或有效指针
在访问链表节点之前，应该先检查节点是否存在，是否已被释放
# 利用哨兵
哨兵（Sentinel）是一个额外的节点，用于简化链表的操作。哨兵节点不存储数据，只起到占位符的作用，通常在链表头或尾部设置。
在链表头部插入节点时，如果没有哨兵节点，需要考虑链表为空的情况，而哨兵节点可以避免这种情况的处理，因为哨兵节点永远存在，链表头指针指向哨兵节点的后继节点即可。
在删除链表中的某个节点时，如果节点是第一个节点，需要特殊处理。而有了哨兵节点，就可以把第一个节点当做普通节点来处理，只需要把哨兵节点的后继节点删除即可。
在使用哨兵节点时，需要保证哨兵节点的指针正确指向链表中的节点，否则会导致程序错误。同时，在遍历链表时，也需要注意跳过哨兵节点。
# 边界问题
空链表：即链表中没有任何结点。在对链表进行操作时，需要特别处理空链表的情况，否则可能会导致程序崩溃。
只有一个结点的链表：如果链表中只有一个结点，需要特别注意处理这种情况，否则可能会导致出现指针丢失或者内存泄露等问题。
头结点和尾结点的处理：在处理链表时，需要注意处理头结点和尾结点的情况。例如，在删除链表中的某个结点时，如果要删除的结点是头结点或者尾结点，需要特别注意处理，否则可能会出现指针丢失或者内存泄露等问题。
特殊位置的处理：有些链表可能会存在一些特殊位置，例如倒数第 k 个结点，需要特别注意处理这些特殊位置的情况，否则可能会导致程序出错。
# 例题讲解
# 前端应用
在前端开发中，链表并不是最常用的数据结构之一，但是在一些特定的场景中，链表还是会被用到 下面列举一些常见的应用场景：
实现DOM结构：DOM树的结构就可以看做是一种树形的数据结构，而树的实现可以借助链表的方式来完成。
实现异步队列：JavaScript中的异步任务通常使用事件循环机制来处理，而事件循环队列就可以用链表来实现。
实现LRU缓存：LRU缓存算法中需要删除最近最少使用的数据，而这个可以通过链表的方式来实现，即将最近访问的元素插入到链表的头部，当需要删除元素时，删除链表尾部的元素即可。
实现动画效果：JavaScript中的动画效果可以通过设置定时器或者使用requestAnimationFrame来实现，而动画帧通常是通过链表的方式来实现。
总之，虽然链表在前端开发中不是最常用的数据结构，但是在一些特定的场景中还是有广泛的应用的。
# leetcode链表经典题目
# 基本操作
- Reverse Linked List（反转链表）
- Merge Two Sorted Lists（合并两个有序链表）
- Remove Duplicates from Sorted List（删除排序链表中的重复元素）
- Linked List Cycle（判断链表是否有环）
# 高级操作
- Swap Nodes in Pairs（两两交换链表中的节点）
- Reverse Nodes in k-Group（k 个一组翻转链表）
- Reverse Linked List II（反转链表 II）
- Reorder List（重排链表）
# 链表变形
- Rotate List（旋转链表）
- Partition List（分隔链表）
- Odd Even Linked List（奇偶链表）