1. 链表的概念

（1）链表的结构

在计算机里，不保存在连续存储空间中，而每一个元素里都保存了到下一个元素的地址的数据结构，我们称之为链表（Linked List）。链表上的每一个元素又可以称它为节点（Node），而链表中第一个元素，称它为头节点（Head Node），最后一个元素称它为尾节点（Tail Node）。
链表的结构定义中，包含了两个信息，一个是数据信息，用来存储数据的，也叫做数据域；另外一个是地址信息，用来存储下一个节点地址的，也叫做指针域。
image.png
可以看到，链表节点以整型作为数据域的类型，其中第一个链表节点，存储了 763 这个数据，指针域中呢，存储了一个 0x56432 地址，这个地址而 0x56432 正是第二个链表节点的地址。这样，第一个节点指向第二个节点，因此这两个节点之间，在逻辑上构成了一个指向关系。
在第二个节点的指针域中呢，存储了一个地址，是 0x0，这个地址值所对应就是 0。这是一个特殊的地址，我们称它为空地址，用 NULL 表示这个空地址。第二个链表节点指向空地址，就意味着它就是这个链表结构的最后一个节点。
链表的定义中包含两个属性，val 用来保存节点上的数据，next用来保存指向下一个节点的链接。使用一个构造函数来创建节点，在构造函数设置了这两个属性的值：

  1. public class ListNode {
  2.     public int val;
  3.     public ListNode next;
  4. }

注意，链表结构的指针域只有一个 next 变量，这说明每一个链表节点，只能唯一地指向后续的一个节点。

（2）链表与数组对比

其实，链表结构和数组结构很类似，只不过数组结构在内存中存储是连续的，链表结构由于有指针域的存在，它的每一个节点在内存中存储的位置未必连续。下面来对比一下两者的性能。

1）空间利用率

数组在创建之后大小是无法改变的，想要增加元素的话就必须重新创建一个新的数组。所以有时为了能够动态地增加元素，在开始创建数组时会声明一个比需要的大小还多的空间出来，以便后面添加新的元素。这个时候就会造成空间上的浪费，所以，数组的空间利用率相当于本来需要的大小除以创建出来数组的大小。
而因为链表中的元素只有当需要的时候才会被创建出来，所以不存在需要多预留空间的情况。对于我们来说，只有节点里的值是可以利用上的，而保存节点地址的内存其实对于我们来说是无法应用的。所以链表的空间利用率上相当于值的大小除以值的大小和节点地址大小的和。

2）时间复杂度

访问数组元素的时间复杂度是 O(1)。而因为链表顺序访问的这个特性，访问链表中第 N 个元素需要从第一个元素一直遍历到第 N 个元素，所以平均下来的时间复杂度是 O(N)。
对于数组来说，插入操作无论是发生在数组结尾还是发生在数组的中间，因为都需要重新创建一个新的数组出来，并复制一遍之前的元素到新的数组中，所以平均的时间复杂度都是 O(N)。而对于链表来说，要是一直都能维护一个尾节点的地址的话，那么插入一个新的元素只需要 O(1) 的时间复杂度。而当插入一个元素到链表中间的时候，因为链表顺序访问的这个特性，需要先遍历一遍链表，从第一个节点开始直到第 N 个位置，然后再进行插入，所以平均下来的时间复杂度是 O(N)。

（3）链表的形式

1）单向链表

所有的链表节点中都只保存了指向下一个节点地址的信息。这种在一个节点中既保存了数据，也保存了指向下一个节点地址信息的链表，称之为单向链表（Singly Linked List）。如下图所示：
image.png

2）双向链表

单向链表有着只能朝着一个方向遍历的局限性，既然可以保存指向下一个节点地址的信息，也可以保存指向上一个节点地址的信息。这种在一个节点中保存了数据也保存了连向下一个和上一个节点地址信息的链表，称之为双向链表（Doubly Linked List）。和链表中尾节点的下一个节点只保存空地址一样，链表中头节点的上一个节点地址也保存着空地址，如下图所示：
image.png

3）循环链表

无论是单向链表或者是双向链表，当遍历至尾节点之后就无法再遍历下去了，如果将尾节点指向下一个节点地址的信息更新成指向头节点的话，这样整个链表就形成了一个环，这种链表称之为循环链表（Circular Linked List）。如下图所示：
image.png

2. 链表的操作

在实现链表时候，通常在链表前面加一个假头，所谓假头，通常也叫作 Dummy Head 或者“哑头”。实际上，就是在链表前面，加上一个额外的结点。此时，存放了 N 个数据的带假头的链表，算上假头一共有 N+1 个结点。
那额外的结点不会存放有意义的数据。那么它的作用是什么呢？
其实，添加假头后，可以省略掉很多空指针的判断，链表的各种操作会变得更加简洁。关于链表的各种操作，主要是以下 6 种基本操作：

  • 链表初始化
  • 尾部追加结点
  • 头部插入结点
  • 查找结点
  • 插入指定位置之前
  • 删除结点

下面以 LeetCode 的707题《设计链表》为例，来实现一下单链表，题目要求将这 6 种基本的操作加以实现：

  1. class MyLinkedList {
  3.     public MyLinkedList() {}
  5.     public int get(int index) {}
  7.     public void addAtHead(int val) {}
  9.     public void addAtTail(int val) {}
  11.     public void addAtIndex(int index, int val) {}
  13.     public void deleteAtIndex(int index) {}
  14. }

707. 设计链表

3. 经典题目

141. 环形链表
142. 环形链表 II
160. 相交链表
876. 链表的中间结点
234. 回文链表
2. 两数相加
445. 两数相加 II
206. 反转链表
92. 反转链表 II
61. 旋转链表
未完成：
24. 两两交换链表中的节点