思路

  • 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;
    }
}