1，通过集合set解决
做这题最容易想到的一种解决方式就是先把第一个链表的节点全部存放到集合set中，然后遍历第二个链表的每一个节点，判断在集合set中是否存在，如果存在就直接返回这个存在的结点。如果遍历完了，在集合set中还没找到，说明他们没有相交，直接返回null即可，原理比较简单，直接看下代码
public class Solution {
public ListNode FindFirstCommonNode(ListNode headA, ListNode headB) {
//创建集合set
HashSet<ListNode> set = new HashSet<>();
//先把链表A的结点全部存放到集合set中
while (headA != null) {
set.add(headA);
headA = headA.next;
}
//然后访问链表B的结点，判断集合中是否包含链表B的结点，如果包含就直接返回
while (headB != null) {
if (set.contains(headB))
return headB;
headB = headB.next;
}
//如果集合set不包含链表B的任何一个结点，说明他们没有交点，直接返回null
return null;
}
}2，先统计两个链表的长度
还可以先统计两个链表的长度，如果两个链表的长度不一样，就让链表长的先走，直到两个链表长度一样，这个时候两个链表再同时每次往后移一步，看节点是否一样，如果有相等的，说明这个相等的节点就是两链表的交点，否则如果走完了还没有找到相等的节点，说明他们没有交点，直接返回null即可，来画个图看一下。
最后再来看下代码
public ListNode FindFirstCommonNode(ListNode headA, ListNode headB) {
//统计链表A和链表B的长度
int lenA = length(headA), lenB = length(headB);
//如果节点长度不一样，节点多的先走，直到他们的长度一样为止
while (lenA != lenB) {
if (lenA > lenB) {
//如果链表A长，那么链表A先走
headA = headA.next;
lenA--;
} else {
//如果链表B长，那么链表B先走
headB = headB.next;
lenB--;
}
}
//然后开始比较，如果他俩不相等就一直往下走
while (headA != headB) {
headA = headA.next;
headB = headB.next;
}
//走到最后，最终会有两种可能，一种是headA为空，
//也就是说他们俩不相交。还有一种可能就是headA
//不为空，也就是说headA就是他们的交点
return headA;
}
//统计链表的长度
private int length(ListNode node) {
int length = 0;
while (node != null) {
node = node.next;
length++;
}
return length;
}3，双指针解决
我们还可以使用两个指针，最开始的时候一个指向链表A，一个指向链表B，然后他们每次都要往后移动一位，顺便查看节点是否相等。如果链表A和链表B不相交，基本上没啥可说的，我们这里假设链表A和链表B相交。那么就会有两种情况，
一种是链表A的长度和链表B的长度相等，他们每次都走一步，最终在相交点肯定会相遇。
一种是链表A的长度和链表B的长度不相等，如下图所示
虽然他们有交点，但他们的长度不一样，所以他们完美的错开了，即使把链表都走完了也找不到相交点。
我们仔细看下上面的图，如果A指针把链表A走完了，然后再从链表B开始走到相遇点就相当于把这两个链表的所有节点都走了一遍，同理如果B指针把链表B走完了，然后再从链表A开始一直走到相遇点也相当于把这两个链表的所有节点都走完了
所以如果A指针走到链表末尾，下一步就让他从链表B开始。同理如果B指针走到链表末尾，下一步就让他从链表A开始。只要这两个链表相交最终肯定会在相交点相遇，如果不相交，最终他们都会同时走到两个链表的末尾，我们来画个图看一下
如上图所示，A指针和B指针如果一直走下去，那么他们最终会在相交点相遇，最后再来看下代码
public ListNode FindFirstCommonNode(ListNode headA, ListNode headB) {
//tempA和tempB我们可以认为是A,B两个指针
ListNode tempA = headA;
ListNode tempB = headB;
while (tempA != tempB) {
//如果指针tempA不为空，tempA就往后移一步。
//如果指针tempA为空，就让指针tempA指向headB（注意这里是headB不是tempB）
tempA = tempA == null ? headB : tempA.next;
//指针tempB同上
tempB = tempB == null ? headA : tempB.next;
}
//tempA要么是空，要么是两链表的交点
return tempA;
}我把部分算法题整理成了PDF文档，截止目前总共有900多页，大家可以下载阅读
链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
京公网安备 11010502036488号