概念
链表是一种常用的数据结构它是由一系列节点组成的，每个节点包含两部分：数据域和指针域。数据域存储节点的数据，指针域存储下一个节点的地址。
种类
链表可以分为单向链表、双向链表和循环链表三种。
单向链表中，每个节点只包含一个指针域，指向下一个节点。
双向链表中，每个节点包含两个指针域，分别指向前一个节点和后一个节点。
循环链表中，最后一个节点的指针域指向第一个节点，形成一个环。
优点
插入和删除元素方便：由于链表节点包含指针域，因此在链表中插入或删除元素只需要修改指针域的指向即可，不需要移动其他元素，因此效率很高。
链表长度可以动态变化：由于链表的内存空间是动态分配的，因此链表长度可以随时增加或减少，不受内存限制。
可以有效利用内存空间：由于链表节点是分散存储在内存中的，因此可以有效利用内存空间，不会造成内存碎片问题。
缺点
随机访问效率低：由于链表节点是通过指针连接起来的，因此无法直接通过下标访问元素，需要从头开始遍历整个链表，效率较低。
存储需要额外空间：由于链表节点需要额外的指针域来存储下一个节点的地址，因此相对于数组等静态数据结构，链表存储需要额外的空间。
链表在很多场景中都有广泛的应用，比如实现栈、队列、图等数据结构，以及字符串匹配算法等。
前端应用
在前端开发中，链表并不是最常用的数据结构之一，但是在一些特定的场景中，链表还是会被用到。下面列举一些常见的应用场景：
- 实现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 个结点，需要特别注意处理这些特殊位置的情况，否则可能会导致程序出错。
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题：反转链表
🔸题目描述：
单链表的反转，是指将单链表中的每个节点的指针指向它的前一个节点。
最终的结果就是原来的尾节点变成了头节点，原来的头节点变成了尾节点
🔸解题思路：
▪️初始化三个指针
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 };