删除链表的倒数第N个节点
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
思路是这样的，但要注意一些细节。
分为如下几步：
-
推荐大家使用虚拟头结点，这样方便处理删除实际头结点的逻辑，
-
定义fast指针和slow指针，初始值为虚拟头结点，如图：
-
fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
-
fast和slow同时移动，直到fast指向末尾，如题：
-
删除slow指向的下一个节点，如图：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//新建一个虚拟头节点指向head
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
//快慢指针指向虚拟头节点
ListNode fastIndex = dummyNode;
ListNode slowIndex = dummyNode;
// 只要快慢指针相差 n 个结点即可
for (int i = 0; i <= n; i++) {
fastIndex = fastIndex.next;
}
while (fastIndex != null) {
fastIndex = fastIndex.next;
slowIndex = slowIndex.next;
}
// 此时 slowIndex 的位置就是待删除元素的前一个位置。
// 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
// 检查 slowIndex.next 是否为 null，以避免空指针异常
if (slowIndex.next != null) {
slowIndex.next = slowIndex.next.next;
}
return dummyNode.next;
}
}链表相交
简单来说，就是求两个链表交点节点的指针。 这里同学们要注意，交点不是数值相等，而是指针相等。
为了方便举例，假设节点元素数值相等，则节点指针相等。
看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：
我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。
否则循环退出返回空指针。
(版本一)先行移动长链表实现同步移动public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0, lenB = 0;
while (curA != null) { // 求链表A的长度
lenA++;
curA = curA.next;
}
while (curB != null) { // 求链表B的长度
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
//1. swap (lenA, lenB);
int tmpLen = lenA;
lenA = lenB;
lenB = tmpLen;
//2. swap (curA, curB);
ListNode tmpNode = curA;
curA = curB;
curB = tmpNode;
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap-- > 0) {
curA = curA.next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}(版本二) 合并链表实现同步移动public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// p1 指向 A 链表头结点，p2 指向 B 链表头结点
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
// p1 走一步，如果走到 A 链表末尾，转到 B 链表
if (p1 == null) p1 = headB;
else p1 = p1.next;
// p2 走一步，如果走到 B 链表末尾，转到 A 链表
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}