题解 | #两个链表的第一个公共结点#

import java.util.HashSet;
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
    this.val = val;
}

}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

    //我能想到的最简单的思路就是：
    //两层循环，依次遍历两个ListNode,当两个链表中，某个节点的下一个节点与另外一个链表中的一个节点的下一个
    //节点相同，那么，直接返回下一个节点，结束
    //《上面这个思路时间复杂度O（n^2）,是暴力解，不好》
    if(pHead1 == null || pHead2==null){
        return null;
    }
    if(pHead1== pHead2){
        return pHead1;
    }
    //【推荐】还有一种思路是：
    //建立一个set，将第一个链表的节点一个个放入set中，然后遍历第二个链表，判断set中时候包含第二个节点
    //如果第二个链表的某个节点已经存在于这个set中，则直接返回即可，程序结束

    //将第一个链表节点放入set中
    HashSet<ListNode> set = new HashSet<>();
    while(pHead1 != null){
        set.add(pHead1);
        if(pHead1.next ==null){
            break;
        }
        pHead1 = pHead1.next;
    }
    //判断节点是否存在于set中
    while(pHead2 != null){
        if(set.contains(pHead2)){
            return pHead2;
        }
        if(pHead2.next == null){
            break;
        }
        pHead2 = pHead2.next;
    }
    return null;
}

}