1.链表链表（LinkedList）是一种常见的基础数据结构，也是一种线性表。线性列表是具有相同特征的n个数据元素的有限序列。线性表的存储结构分为顺序表（数组）和链表两大类。与顺序表相比，链表不是按线性顺序存储数据，而是在每个节点中存储一个指向下一个节点的指针。在JavaScript中，我们可以这样描述链表中的节点：2.链表与数组不同的存储方式：在使用数组之前，需要申请占用内存的大小，它是一块连续的内存区域，不适合动态存储。正是因为连续的内存存储，随机访问数组的时间复杂度为O(1)。链表克服了数组需要事先知道数据大小的缺点，可以充分利用内存空间，实现动态内存管理。但是由于每个节点都增加了一个指针字段，所以空间开销比较大。操作时间复杂度的区别：数据类型读取时间复杂度写入时间复杂度链表O(n)O(1)数组O(1)O(n)从存储方式分析可知数组具有随机性可以访问，但是访问链表中的元素需要遍历链表，所以时间复杂度是O(n)。链表中的写操作只需要断开当前节点的前驱节点和后继节点的指针，所以时间复杂度为O(1)。但是由于数组连续存储的特点，写入操作并不是那么简单。以删除数组第一个元素为例，数组需要执行以下两个步骤：删除第一个元素。O(1)从第二个元素开始，依次向前移动一位。O(n)所以对于任意位置的写入，虽然链表需要先进行O(n)的遍历才能定位到元素，但是整体效率还是高于数组的。三、Easy典型题型分析1.【1290.二进制链表转整数】给你一个单链表的参考节点头。链表中每个节点的值要么为0，要么为1。已知该链表是整数的二进制表示。请返回链表所代表的数的十进制值。本题主要考察链表遍历的基本操作：迭代链表节点的next指针。2.[876。链表中间节点】给定一个非空单链表，其头节点为head，返回链表中间节点。如果有两个中间节点，则返回第二个中间节点。解决这个问题比较实际的思路是：第一次遍历找到链表的长度，从而计算中间位置，第二次遍历根据中间位置找到中间节点。下面给出的解决方案是经常使用的双指针技术中的快慢指针，巧妙地解决了中间节点：3.[83.删除排序链表中的重复元素]给定一个排序链表，删除所有重复元素，使每个元素只出现一次。由于本题链表是排序链表，所以只考察删除链表中节点的操作：通过改变目标节点的前驱节点的next指针来删除目标节点。参考视频：传送门4，【206.ReverseLinkedList]反转一个单向链表。第一种方案：先遍历链表得到翻转链表节点值数组，然后遍历链表替换节点的值。第二种方案，利用链表的特性，简化为一次遍历完成翻转操作。以上面链表为例，翻转过程如下：解题代码如下：5.[141.环形链表】给定一个链表，判断链表中是否存在环。第一种方案：遍历链表，使用HashMap记录节点对象，如果有重复节点，则有环。第二种方案是在双指针中使用快慢指针技术：当链表中有环时，快指针必须能够追上慢指针。
