概念
链表是一种常用的数据结构它是由一系列节点组成的，每个节点包含两部分：数据域和指针域。数据域存储节点的数据，指针域存储下一个节点的地址。
种类
链表可以分为单向链表、双向链表和循环链表三种。
- 单向链表：每节点只包含一个指针域，指向下一节点。
- 双向链表：每节点包含两个指针域，分别指向前一节点和后一节点。
- 循环链表：最后一节点的指针域指向第一个节点，形成一个环。
优点
- 插入和删除效率高：由于链表节点包含指针域，因此在链表中插入或删除元素只需要修改指针域的指向即可，不需要移动其他元素，因此效率很高。
- 动态维护：由于链表的内存空间是动态分配的，因此链表长度可以随时增加或减少，不受内存限制。
- 有效利用内存：由于链表节点是分散存储在内存中的，因此可以有效利用内存空间，不会造成内存碎片问题。
缺点
- 随机访问效率低：无法通过下标直接访问，需顺序遍历。
- 增加较多内存占用：每个节点需要额外的指针域，占用更多资源。
前端应用
在前端开发中，链表并不是最常用的数据结构之一，但是在一些特定的场景中，链表还是会被用到。下面列举一些常见的应用场景：
- DOM结构的实现：DOM树的结构就可以看做是一种树形的数据结构，而树的实现可以借助链表的方式来完成。
- 实现异步队列：JavaScript中的异步任务通常使用事件循环机制来处理，而事件循环队列就可以用链表来实现。
- 实现LRU缓存：LRU缓存算法中需要删除最近最少使用的数据，而这个可以通过链表的方式来实现，即将最近访问的元素插入到链表的头部，当需要删除元素时，删除链表尾部的元素即可。
- 实现动画效果：JavaScript中的动画效果可以通过设置定时器或者使用requestAnimationFrame来实现，而动画帧通常是通过链表的方式来实现。
难点
1. 理解链表的指向
就拿基础的单链表来说，每个节点有一个指向域（指针），指向下一个节点。
这个指向的作用是连接链表中的节点，使得节点之间可以通过指针相互访问和操作。
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针（指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量）
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 节点被删除了。
2. 注意指针丢失、指针越界、内存泄露
在链表中，每个节点的指针都是存储在内存中的，因此在使用指针时，需要注意空指针和野指针等安全问题
- 指针丢失：一个指针指向了一个动态分配的内存块，但在后续的程序执行过程中，该指针的值被改变，无法再访问原本指向的内存块
- 指针越界：访问链表中不存在的节点时，比如，访问链表中的第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指针，以使其指向被删除节点的下一个节点。如果没有更新指针，就会导致链表出现错误的指针引用，甚至出现内存泄漏
- 在使用指针前将其初始化为空指针或有效指针
- 在访问链表节点之前，应该先检查节点是否存在，是否已被释放
3. 利用哨兵
哨兵（Sentinel）是一个额外的节点，用于简化链表的操作。哨兵节点不存储数据，只起到占位符的作用，通常在链表头或尾部设置。
- 在链表头部插入节点时，如果没有哨兵节点，需要考虑链表为空的情况，而哨兵节点可以避免这种情况的处理，因为哨兵节点永远存在，链表头指针指向哨兵节点的后继节点即可。
- 在删除链表中的某个节点时，如果节点是第一个节点，需要特殊处理。而有了哨兵节点，就可以把第一个节点当做普通节点来处理，只需要把哨兵节点的后继节点删除即可。
在使用哨兵节点时，需要保证哨兵节点的指针正确指向链表中的节点，否则会导致程序错误。同时，在遍历链表时，也需要注意跳过哨兵节点。
4. 边界问题
- 空链表：即链表中没有任何结点。在对链表进行操作时，需要特别处理空链表的情况，否则可能会导致程序崩溃。
- 只有一个结点的链表：如果链表中只有一个结点，需要特别注意处理这种情况，否则可能会导致出现指针丢失或者内存泄露等问题。
- 头结点和尾结点的处理：在处理链表时，需要注意处理头结点和尾结点的情况。例如，在删除链表中的某个结点时，如果要删除的结点是头结点或者尾结点，需要特别注意处理，否则可能会出现指针丢失或者内存泄露等问题。
- 特殊位置的处理：有些链表可能会存在一些特殊位置，例如倒数第 k 个结点，需要特别注意处理这些特殊位置的情况，否则可能会导致程序出错。
解题技巧
1. 明确链表题的本质
链表是一个节点相连的数据结构，每个节点包含两个部分：
- 值（value）
- 指针（next）：指向下一个节点。
理解链表操作的关键是：每次操作的目标是控制“指针”改变方向或继续遍历。
关键问题：
- 需要操作节点的“值”还是操作节点的“指针”？
- 需要修改链表结构还是只是遍历？
2.常见的链表赋值和头节点处理
每次写链表题目时，通常需要明确以下几个操作：
（1）头节点的处理
- 如果链表给的是一个已有的头节点 head，直接用它进行操作即可
- 如果链表需要你手动初始化，比如合并链表或构建链表：
- 通常会创建一个虚拟头节点（dummy node），便于操作。例如：
let dummy = new ListNode(-1); // 创建虚拟头节点 let curr = dummy; // 初始化当前节点指针为 dummy
（2）遍历链表的基础模板
链表的遍历非常重要，通常写成以下形式：
let curr = head; // curr 指向当前节点，初始为 head while (curr !== null) { console.log(curr.val); // 处理当前节点值 curr = curr.next; // 移动到下一个节点 }
（3）改变链表结构
当需要插入、删除、反转节点时，操作的本质是修改节点的 next 指针。最常见的模板是：
let prev = null; // 反转链表时需要前一个节点 let curr = head; // 当前节点 while (curr !== null) { let nextTemp = curr.next; // 保存下一个节点 curr.next = prev; // 改变当前节点的指向 prev = curr; // 前进一步，更新 prev curr = nextTemp; // 前进一步，更新 curr }
3. 写链表题时的思考顺序
（1）题目目标是什么？
- 是遍历链表？
- 修改链表结构（如反转、合并、删除）？
- 检测某些性质（如是否有环）？
（2）从哪里开始？
- 如果需要操作头节点，明确是否需要处理特殊情况（例如链表为空）
- 如果需要返回一个新链表，通常会创建一个虚拟头节点（dummy）
（3）需要什么指针？
- 一个遍历指针（如 curr）负责移动
- 需要辅助指针（如 prev 或 nextTemp）时，明确它的作用
（4）特殊边界情况？
- 链表为空
- 链表只有一个节点
- 链表是偶数节点还是奇数节点（如找中点）
4. 总结：怎么找到下手点
- 记住通用模板：
- 遍历链表
- 改变节点指针的方向
- 善用辅助节点：如虚拟头节点（dummy）
- 对链表题多实践：
- 从简单的反转链表、合并链表开始。
- 再挑战环形链表、LRU 缓存等复杂问题。
- 分析题目：多画图
- 动手画链表节点的变化，帮助理解操作。
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（奇偶链表）
例题讲解
206题：反转链表
题目描述：
单链表的反转，是指将单链表中的每个节点的指针指向它的前一个节点。
最终的结果就是原来的尾节点变成了头节点，原来的头节点变成了尾节点
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
解题思路：
- 初始化三个指针
prev、cur和temp，其中prev和temp都是 null，而cur是头节点
- 遍历链表。每次将
cur的指针指向prev，然后将三个指针都向后移动一个节点
具体来说，对于每个节点，我们先将它的
temp 指针指向它的前一个节点（先存起来），然后将三个指针都往后移动一个节点- 最后，
prev就是反转后的头节点，而cur是 null，即反转后的尾节点，输出prev
执行过程
假设我们有一个单链表：
1 -> 2 -> 3 -> 4 -> 5，现在要对它进行反转第一步
当前
prev=null, cur = head，head→1,也就是cur→1，也就是cur.next=1因为我们要进行反转，也就是1指向nul才对，这时候
prev=nul所以是
cur.next=prev，也就是1→null在难点中说了我们要注意指针丢失，大家可以思考下，上面的步骤有什么不对吗？
没错，就是1→2的这段指针丢了，为什么呢？
1原本是指向2的，然后现在变成指向null了，那谁指向2呢？
所以，我们要将1→2这个指针先存起来，也就是
temp=cur.next.next // 1.next=2, 1=cur.next, 所以cur.next.next=2
第二步
将1指向null，也就是
cur.next=prev第三步
prev本来是指向null的，现在要将它往前一步，所以要指向
head看一下第一步，谁是head？是
cur！！！也就是prev=cur第四步
大家都往前走了一步，cur也要往前一步，本来cur.next是1，现在应该是2了
而2刚才在第一步的最后被我们存起来了，也就是
temp，所以cur=temp总结
所以，遍历的步骤就是
temp=cur.next.nextcur.next=prevprev=curcur=temp结束过程
一直走到最后，cur=null后就结束，也就是while(cur != null)
注意点
这题如果要提升性能还要考虑边界问题，链表可能是空链表或者只有一个节点的链表
所以，在while的最前面，要做个判断
if (head == null || head.next == null) return head;解法2
上面是迭代法，还可以用递归法，递归法的思路相对简单。
我们先将当前节点的下一个节点作为参数传递进去递归，然后再将当前节点的 next 指针指向前一个节点。
递归终止条件是当前节点为空或者当前节点的下一个节点为nul
多画图，每一步往下走，配合图更容易理解
单链表的反转，是指将单链表中的每个节点的指针指向它的前一个节点。最终的结果就是原来的尾节点变成了头节点，原来的头节点变成了尾节点。
例如，假设我们有一个单链表：
1 -> 2 -> 3 -> 4 -> 5，现在要对它进行反转。我们可以按照如下的方式进行：- 初始化三个指针
prev、cur和next，其中prev和next都是 null，而cur是头节点。
- 遍历链表，每次将
cur的指针指向prev，然后将三个指针都向后移动一个节点。具体来说，对于每个节点，我们先将它的next指针指向它的前一个节点，然后将三个指针都往后移动一个节点。这个过程可以用如下的伪代码来表示：
while (cur != null) { next = cur.next cur.next = prev prev = cur cur = next }
- 最后，
prev就是反转后的头节点，而cur是 null，即反转后的尾节点。
例如，对于链表
1 -> 2 -> 3 -> 4 -> 5，上述算法的执行过程如下所示：prev cur next null 1 -> 2 -> 3 -> 4 -> 5 -> null | | | | | +---------+ | | | | | | | +-----+ | | | | | +----+ | | | +----+ prev cur next 1 <- 2 3 -> 4 -> 5 -> null | | | | | +---------+ | | | | | | | +-----+ | | | | | +----+ | prev cur next 1 <- 2 <- 3 4 -> 5 -> null | | | | | +---------+ | | | | | | | +-----+ | | | | | +----+ | prev cur next 1 <- 2 <- 3 <- 4 5 -> null | | | | +---------+ | | | | | +-----+ | | | +---------+ prev cur next 1 <- 2 <- 3 <- 4 <- 5 null | | | +---------+ | | | +----------+
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { if(head == null || head.next == null) return head let prev = null let curr = head while(curr !==null){ let temp = curr.next curr.next = prev prev = curr curr = temp } return prev };