链表作为一种数据结构，它存放着有序元素的集合。元素与元素之间通过指针连接，因此在链表中添加或删除元素只需要修改指针的指向即可，执行速度相比数组有得到显著的提升。
现实生活中也有许多使用到链表的例子，例如兔子舞，每个人勾肩搭背组合而成，其中人相当于链表中的元素，勾肩搭背的手相当于链接每个人的指针，在队列中加入一个人，只需要找到想加入的点，断开连接，插入一个人再重新连接起来。
说链表就不得不提数组，它和数组可以说是数据结构的基础，那么它们最主要的区别在于：
- 数组在物理内存上必须是连续的
- 链表在物理内存上不需要连续，通过指针连接
所以数组最好的性质就是可以随机访问 random access，有了 index，可以 O(1) 的时间访问到元素。
而链表因为不连续，所以无法 O(1) 的时间定位任意一个元素的位置，那么就只能从头开始遍历。
LinkedList 是由 ListNode 来实现的：
class ListNode {
int value;
ListNode next;
}
双向链表和单向链表的不同就是，它还有一个 previous pointer 指向当前 node 的前一个 node：
class ListNode {
int value;
ListNode next;
ListNode prev;
}
双指针法在很多数据结构和题型中都有应用，在链表中用的最多的还是快慢指针。
顾名思义，两个指针一个走得快，一个走得慢，这样的好处就是以不同的速度遍历链表，方便找到目标位置。
常见的问题比如找一个链表的中点，或者判断一个链表是否有环。
这题就是给一个链表，然后找到它的中点，如果是奇数个很好办，如果是偶数个，题目要求返回第二个。 比如： 1 -> 2 -> 3 -> 4 -> 5 -> NULL，需要返回 3 这个 ListNode； 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL，需要返回 4 这个 ListNode。
解法：
我们用两个指针一起来遍历这个链表，每次快指针走 2 步，慢指针走 1 步，这样当快指针走到头的时候，慢指针应该刚好在链表的中点。
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
思路：快慢指针一起从 head 出发，每次快指针走 2 步，慢指针只走 1 步，如果存在环，那么两个指针一定会相遇。
这题是典型的龟兔赛跑，或者说在操场跑圈时，跑的快的同学总会套圈跑的慢的。
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {
return true;
}
}
return false;
}
}
Dummy 的中文是“假”的意思，dummy node 大概可以翻译成虚拟节点？
一般来说，dummy node 的用法是在链表的真实 head 的前面加一个指向这个 head 的节点，目的是为了方便操作 head。
对于链表来说，head 是一个链表的灵魂，因为无论是查询还是其他的操作都需要从头开始，俗话说擒贼先擒王嘛，抓住了一个链表的头，就抓住了整个链表。 所以当需要对现有链表的头进行改动时，或者不确定头部节点是哪个，我们可以预先加一个 dummyHead，这样就可以灵活处理链表中的剩余部分，最后返回时去掉这个“假头”就好了。
这题有很多种解法，比如最直观的就是用两个指针，然后比较大小，把小的接到最终的结果上去。
但是有点麻烦的是，最后的结果不知道到底谁是头啊，是哪个链表的头作为了最终结果的头呢？
这种情况就非常适合用 dummy node。先用一个虚拟的头在这撑着，把整个链表构造好之后，再把这个假的剔除。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode dummy = new ListNode(0);
ListNode ptr = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
ptr.next = l1;
l1 = l1.next;
} else {
ptr.next = l2;
l2 = l2.next;
}
ptr = ptr.next;
}
if (l1 == null) {
ptr.next = l2;
} else {
ptr.next = l1;
}
return dummy.next;
}
}
这道题的意思是删除链表中某个特定值的节点，可能有一个可能有多个，可能在头可能在尾。
如果要删除的节点在头的时候，新链表的头就不确定了，也有可能是个空的。。此时就很适合用 dummy node 来做，规避掉这些 corner case 的讨论。
那这题的思路就是：用 2 个指针 - prev：指向当前新链表的尾巴 - curr：指向当前正在遍历的 ListNode
如果 curr == 目标值，那就直接移到下一个；
如果 curr != 目标值，那就把 prev 指向它，接上。
这题需要注意的是，最后一定要把 prev.next 指向 null，否则如果原链表的尾巴是目标值的话，还是去不掉。
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
ListNode prev = dummy;
ListNode curr = head;
while(curr != null) {
if (curr.val != val) {
prev.next = curr;
prev = prev.next;
}
curr = curr.next;
}
prev.next = null;
return dummy.next;
}
}