一、链表
链表（Linked List）是一种常见的根底数据结构，也是线性表的一种。
一个线性表是 n 个具备雷同个性的数据元素的无限序列，线性表的存储构造分为两类：程序表（数组）和链表。
链表相比拟程序表，它并不会依照线性的顺序存储数据，而是在每个节点里存储到下一个节点的指针，在 JavaScript 中，咱们能够这样形容链表中的节点：
二、链表 vs 数组
存储形式 的不同：
- 数组在应用前须要先申请占用内存的大小，并且是 间断的内存区域 ，不适宜 动静存储 ，正是因为间断内存存储，使得 数组随机拜访的工夫复杂度为 O(1)。
- 链表则克服了数组须要事后晓得数据大小的毛病，能够充沛地利用内存空间，实现 动态内存治理 ，然而因为每个节点减少了指针域， 空间开销比拟大。
操作工夫复杂度 的不同：
| 数据类型 | 读取工夫复杂度 | 写入工夫复杂度 |
|---|---|---|
| 链表 | O(n) | O(1) |
| 数组 | O(1) | O(n) |
后面从存储形式的剖析中，能够晓得数组具备随机拜访的能力，然而拜访链表中的元素则须要遍历链表，因而工夫复杂度为 O(n)。 链表中写入操作只须要将以后节点的前驱和后继节点的指针断开即可，所以工夫复杂度为 O(1)。 然而因为数组是间断内存的个性，写入操作并没有那么简略，以删除数组首位元素为例，数组须要执行以下两步操作：
- 删除首位元素。O(1)
- 从第二位元素开始，顺次向前挪动一位。O(n)
所以对于任意地位的写入，链表尽管须要先执行 O(n) 的遍从来定位元素，然而它的整体效率依然比数组高。
三、Easy 典型题型剖析
1、【1290. 二进制链表转整数】
给你一个单链表的援用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制示意模式。请你返回该链表所示意数字的 十进制值。
这道题目次要考查链表遍历的基本操作：迭代链表节点的 next 指针。
2、【876. 链表的两头结点】
给定一个带有头结点 head 的非空单链表，返回链表的两头结点。如果有两个两头结点，则返回第二个两头结点。
这道题目比拟切实的解题思路是：第一次遍历求出链表长度，从而计算出两头地位，第二次遍历依据两头地位找出两头节点。
上面给出的解法，是常常用到的 双指针技巧中的快慢指针，奇妙地求解出两头节点：
3、【83. 删除排序链表中的反复元素】
给定一个排序链表，删除所有反复的元素，使得每个元素只呈现一次。
因为本道题目中的链表是一个排序链表，所以只考查了链表中删除节点的操作：扭转指标节点的前驱节点的 next 指针，即可删除指标节点。参考视频：传送门
4、【206. 反转链表】
反转一个单链表。
第一种解法：先遍历链表获取翻转后的链表节点值的数组，再遍历链表替换节点的值。
第二种解法，利用链表的个性，简化为一次遍历实现翻转操作。
以下面的链表为例，翻转流程如下：
解题代码如下：
5、【141. 环形链表】
给定一个链表，判断链表中是否有环。
第一种解法：遍历链表，利用 HashMap 记录节点对象，如果呈现反复的节点则有环。
第二种解法是采纳双指针中的快慢指针技巧：当链表中存在环时，快指针必然能追上慢指针。