链表

链表也是多个元素的集合，但是这些元素在内存中并不是连续存储，而是通过额外存储的下一个节点指针来实现逻辑上的顺序连接。链表的节点一般由两个部分组成，一是数据，二是指向下一个节点的指针。链表有以下特点。

1. 链表中的元素在内存上是不连续存储。
2. 无需提前申请空间，链表长度自由扩展。

链表的优点有，删除和插入元素效率高，时间复杂度是O(1)，但是访问特定节点效率低，需要逐个节点遍历。

例如，链表[1,2,3,4,5,6,7,8,9,10]的存储结构如下：

链表也是非常基础的数据结构，很多其它数据结构的底层数据存储方式都可以用链表来实现。比如说List、Stack、Queue等等。

常见的链表有以下这些。

• 单链表，没有特殊说明，一般指的就是单链表。
• 双向链表，相比单链表，在每个节点多加一个指向上一个节点的指针，这样就能够更灵活的操作链表。
• 循环链表，将非循环链表的最后一个节点的next指针指向第一个节点，形成一个环路，就是循环链表，从循环链表的任何一个节点出发都能遍历整个链表。

跟链表相关的题目，最经典的应该就是下面这道链表反转的题目。

反转链表

给你单链表的头节点head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

链表可以选用迭代或递归方式完成反转。

另外一道经典的题目，检测链表是否有环。

环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true

3→2→0→-4
     ↑_____↓

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true

1→2
↑_↓

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false

解释：链表中没有环。

提示：

• 链表中节点的数目范围是 [0, 10^4]
• -10^5 <= Node.val <= 10^5
• pos 为 -1 或者链表中的一个 有效索引 。

判断是否有环，实际上也可以理解为链表节点是否会重复，所以最容易想到的是遍历链表，然后用哈希表来判断节点是否有重复，这种解法空间复杂度为O(N)。下面介绍一种O(1)的解法，还是用之前提到的双指针的技巧，准确来讲应该叫快慢指针，因为每一轮循环第一个指针（快指针）会走两步，而慢指针只走一步，这样如果链表有环的话，两个指针最终会在同一个节点相遇。