# 单链表
双指针的经典应用（快慢指针）
如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
当要把链表分成两部分处理时，可以使用快慢指针法，控制快指针走到链表结(null)，慢指针走到分割链表的地方，
判断链表是否有环，如果有环，则快慢指针终会相遇（相等），循环结束，如果无环，则快慢指针最终都会为空（相等），循环结束。记录当前相遇的位置，再定义两个指针，一个从头开始，一个从当前相遇位置开始，每一步走一个结点，相遇的地方即是环的起点。
基本上所有的题都可以考虑使用虚拟头结点dummy，方便处理算法过程中链表为空的状态（从虚拟头结点出发，便于处理head.next.next这种情况,因为如果head.next已经为空,next.next就无意义了），此时无法获取head.next（算法中一般都会有head.next操作，所以会报错），但可以获取dummy.next, 通过dummy.next就可以输出原链表。
链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。
每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。
数组可以用来模拟链表，需要额外开辟空间
链表相交问题（相交的不是指某个结点的值相等，而是这个结点本身的引用），如果是两个链表，则相当于用两个指针来遍历这两个链表的总长度（两个指针都是从一个链表开始遍历，遍历完这个链表后再从剩下的一个链表的头结点开始遍历），如果二者相等则退出循环，因为遍历长度都一样，所以最后二者一定都为空，循环一定会结束，如果二者相交，循环也结束，返回指针指的结点。