链表简介
链表，是存储空间不连续的线性表。在做题或者一些底层结构挺常见的，但是在开发中好像用得很少（可能我比较菜0-0...）。一个简单的带头结点的单链表可以表示成这样：
class SingleLinkedList{
// 只有一个头结点
private Node head;
// ...
class Node{
Object data;
Node next;
// ...
}
}
简单地说，它的存储结构是一个一个地结点，每个结点中有你想存储的信息，同时还有指向下一个结点（next）的引用。
如果想要在此查找元素的话，就通过next结点进行遍历，直到为空。
链表有很多分类，比如是否带头尾结点，是否是双向链表，是否是循环链表等等，每种分类都对应着不同的特点，有特定的应用场景。
它最大的特点是，寻找元素需要结点中的next指针，一个一个地往下找。即使使用双向链表，它也需要遍历N/2个元素，因此查询的时间复杂度在O(N)。
但是，如果你定位到某个元素，要进行删除的话，只要O(1)的时间复杂度，不需要像数组一样把后面的元素全部移动一位，因为它的数据组成只依靠额外的引用指针。
注意事项
理解指针/引用
这让我想到一些值传递/引用传递相关知识， 就是理解一下Node next的含义。
比如，p.next = newNode，它表示让p这个Node结点的next指针指向newNode这个结点，也就是指向了newNode所在的内存地址。这样操作之后，p就能通过next成员变量找到下一个结点的位置，也就是这个newNode。
需要好好理解这个指针的引用，举个例子，我想要在a、b结点中插入一个新结点newNode，其中a.next=b。
如果写成这样
a.next = newNode;
newNode.next = a.next;
这样做会整出一个循环。。
在改变a的next指针指向newNode时，你就会丢失了对b结点的指向，也就是说，对于一条单链表，在进行如上操作后，已经没有结点能够指向b了，也就丢失了b的结点。
正确的指向应该是解决b相关的引用，然后再断开链表。（要这么想，一旦修改了引用，如果没有保存，那就再也找不到了）
newNode.next = a.next;
a.next = newNode;
哨兵
这个分为两层概念，一层是指头、尾结点，另一层指在算法中一些比较上的优化？
对于一个单链表，它分为有头结点的和有头指针的。
头结点，是指一个空的结点，从数值上，它没有任何意义，仅仅充当着第一个真正存储数据的前一个结点。
而头指针的，只是一个指向第一个元素的指针，不是真正的结点。
头结点有什么好处呢？它可以方便边界条件的处理，在增/删操作中，如果只有头指针的话，会对第一个结点的操作进行特殊判断，但是有了头结点就不同，因为固定有一个结点在，我对头结点的next进行操作，因为总是有头结点在，因此，第一个结点也不会显得很特殊。
带头结点时，对于插入操作，可以统一地用这两行实现
newNode.next = p.next;
p.next = newNode;
这个p则是指向要删除结点的前一个结点。对于第一个结点，它的前一个结点是头结点；对于第k个结点，它的前一个结点是k-1个结点。它们之前没什么不同嘛。而如果没有头结点，就要做一些特殊处理了，比如head = newNode;
我在文章中发现哨兵还有这种用法，展示一下。
下面是普通的查找元素。
// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
int find(char* a, int n, char key) {
// 边界条件处理，如果 a 为空，或者 n<=0，说明数组中没有数据，就不用 while 循环比较了
if(a == null || n <= 0) {
return -1;
}
int i = 0;
// 这里有两个比较操作：i<n 和 a[i]==key.
while (i < n) {
if (a[i] == key) {
return i;
}
++i;
}
return -1;
}
下面是加了哨兵的查找元素。
// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
// 我举 2 个例子，你可以拿例子走一下代码
// a = {4, 2, 3, 5, 9, 6} n=6 key = 7
// a = {4, 2, 3, 5, 9, 6} n=6 key = 6
int find(char* a, int n, char key) {
if(a == null || n <= 0) {
return -1;
}
// 这里因为要将 a[n-1] 的值替换成 key，所以要特殊处理这个值
if (a[n-1] == key) {
return n-1;
}
// 把 a[n-1] 的值临时保存在变量 tmp 中，以便之后恢复。tmp=6。
// 之所以这样做的目的是：希望 find() 代码不要改变 a 数组中的内容
char tmp = a[n-1];
// 把 key 的值放到 a[n-1] 中，此时 a = {4, 2, 3, 5, 9, 7}
a[n-1] = key;
int i = 0;
// while 循环比起代码一，少了 i<n 这个比较操作
while (a[i] != key) {
++i;
}
// 恢复 a[n-1] 原来的值, 此时 a= {4, 2, 3, 5, 9, 6}
a[n-1] = tmp;
if (i == n-1) {
// 如果 i == n-1 说明，在 0...n-2 之间都没有 key，所以返回 -1
return -1;
} else {
// 否则，返回 i，就是等于 key 值的元素的下标
return i;
}
}
这个哨兵有什么好处呢？这段代码只是拿最后一个元素替换成要查找的元素，拿最后一个位置当“哨兵”，但和之前的i<n的循环比，也还是要比较到最后呀，好像没差。
它优化的是while循环的判断语句，第一段代码是在while中先判断下标是否在范围内，然后再判断该下标的值是否为我所想要的值；而第二段代码则直接判断值，然后循环+1下标。这就是它优化的点。
不过，这也让它可读性很差。。
多画图
对的，多画图！
对于链表的操作，如果在草稿纸中画出结点的状态、变化的顺序等，那你将很清晰地看到它是如何变化的，也就很容易理解它这做法。
markdown中不容易画图，这里只是简要记录一下。我在做链表的题目时，都是画画图就知道怎么做了。
LinkedList源码
我错了！我一直以为LinkedList里面是带头尾结点的双向链表，其实它是头尾指针的双向链表，两个指针分别指向的是第一个元素和最后一个元素，并且在增、删的时候进行特殊操作。这也能理解，毕竟是JDK，要效率，我之前是怎么自以为是头尾结点。。。
成员变量如下
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
发现它真的是挺多操作方法的，链表的两端都可以操作，看看它的UML图，知道它实现了Deque接口。
可以看看它的头尾指针的增删是怎么做的，只有指针，它的操作肯定是繁琐的，不过空间上省了两个结点，对于JDK这样的常用集合类来说，还是值得的？
addFirst()与addLast()
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
public void addLast(E e) {
linkLast(e);
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
可以看到，在头、尾添加元素，只需改变头、尾指针的指向即可，操作非常方便。
我学习到了构造函数里面也能设置prev和next指针，之前没想到，还以为少了一些操作。
还有就是，不要忘了这是带头、尾指针的双向链表，在没有元素的时候，第一次插入元素要让两个指针都指向第一个元素。要是我写的话可能会忘了……
removeFirst()与removeLast()
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
同理了，就不粘了。
不过它代码写得确实精妙啊，我写不出来这么妙的代码，真是简洁又明了。
leetcode刷题
练习题LeetCode对应编号：206，141，21，19，876。
把它们都能做出来，链表的基本操作也就搞定了。
我确实也会做了，这算掌握得怎样啊？。。。依然感觉自己菜菜
206. 反转链表
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
141. 环形链表
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}
21. 合并两个有序链表
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode sentinel = new ListNode(0);
ListNode cur = sentinel;
while(list1 != null && list2 != null){
if(list1.val <= list2.val){
cur.next = list1;
cur = list1;
list1 = list1.next;
}else{
cur.next = list2;
cur = list2;
list2 = list2.next;
}
}
if(list1 != null){
cur.next = list1;
}else{
cur.next = list2;
}
return sentinel.next;
}
}
19. 删除链表的倒数第 N 个结点
public ListNode removeNthFromEnd(ListNode head, int n) {
// 保证删除时不报空
if (head == null){
return null;
}
// 哨兵
ListNode sentinel = new ListNode(0);
sentinel.next = head;
ListNode slow = sentinel, fast = head;
// 先让快指针走n步
for(int i = 0;i < n;i++){
fast = fast.next;
}
// 与慢指针一同向前
// 当快指针走到结尾时，慢指针指向要删除元素的前一个
while(fast != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return sentinel.next;
}
876. 链表的中间结点
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.next;
}