1 链表简介
说起链表，我们脑海中浮现出它的样子如下图所示，总是一个节点连着下一个节点。
2 快慢指针的妙用
我们先来简单介绍一下何为快慢指针。快慢指针就是定义两根指针，移动的速度一快一慢，以此来制造出自己想要的差值。这个差值可以让我们找到链表上相应的节点。
如果现在对这里的简介不是很理解，没有关系，我们一起来看看如下的几个例子。相信看完后，就会明白了。
2.1 找中间值
一般的思路是：先遍历一次链表，记录住一共有多少个节点，然后，再次遍历找寻中点。
利用快慢指针，我们来看看这个问题会变成什么样。思路如下：我们把一个链表看成一个跑道，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以此来达到找到中间节点的目的。
如下图，最开始，slow与fast指针都指向链表第一个节点，然后slow每次移动一个指针，fast每次移动两个指针。
2.2 判断链表中的环
还是把链表比作一条跑道，链表中有环，那么这条跑道就是一条圆环跑道，在一条圆环跑道中，两个人有速度差，那么迟早两个人会相遇，只要相遇那么就说明有环。
为了不失一般性，我们在环上加了额外的两个节点，我们可以想象一下，只要两个指针跑进了环里，那么因为存在速度差，他们之间的距离总会由远及近，然后相遇，在远离。像极了我们人世间某些人在你生命中匆匆而过的感觉。
代码如下：
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode fast = head;
ListNode low = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
low = low.next;
if (low.equals(fast)) {
return true;
}
}
return false;
}
2.3 删除倒数第n个节点
删除倒数第n个节点，那就等于是要我们先找出待删除元素前一个元素，也就是第n-1个节点。聪明的你肯定发现了，我们又把这个问题转化为找链表上的某个节点的问题了，这是快慢指针最擅长的场景。
那如何找第(n-1)个元素呢？我们一开始就让fast指针比slow指针快n+1个元素，接下来，两个指针都是一步一步来往下走。那么当fast指针走完时，slow指针就刚刚好停留在第(n-1)个元素上。
以下图解了n=2时的情形（其中dummyHead是我们手动加上去的虚拟头节点）：
最后附上代码：
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null || head.next == null) {
return null;
}
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode slow = dummyHead;
ListNode fast = dummyHead;
for (int i = 0; i < n + 1; i++) {
fast = fast.next;
}
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
转载地址