剑指offer-36-求两个链表汇聚点

思路

• Hash 查找就用Hash,显而易见
• 两个链表相交，链表是单向的，所以两个链表是汇聚的，两条小河汇聚成一条河，求汇聚点。这样有又分两种：
  • 第一种思路转换问题，让一个链表与它的尾部相连，这就转换成了一个带有循环链表的入口问题，后面有这样的题，暂时不提。
  • 另一种思路是求差，也就是找到同步点，求到差div之后，长的链表先走div步，然后开始同步走。

代码

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Set<ListNode> set=new HashSet<>();
        while(pHead1!=null){
            set.add(pHead1);
            pHead1=pHead1.next;
        }
        while(pHead2!=null){
            if(set.contains(pHead2)){
                return pHead2;
            }
            pHead2=pHead2.next;
        }
        return null;
    }
}