算法1

(哈希表) $O(n)$

用哈希表，先把A链表放进去，然后遍历B链表，如果B链表中哪一个值放入失败，就说明重复了，就是入口的节点

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        if(headA==null||headB==null)
            return null;

        while(headA!=null){
            set.add(headA);
            headA = headA.next;
        }
        while (headB!=null){
            if(!set.add(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}

算法2

(同时移动) $O(n)$

先求出两条链表的长度差，然后让长的先走长度差，然后一起移动，就可以找到入口了

java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {


    public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {

        if(headA==null||headB==null)
            return null;
        int h = 0;
        ListNode node = headA;
        while(node!=null){
            node = node.next;
            h++;
        }
        node = headB;
        while (node!=null){
            node = node.next;
            h--;
        }

        if(h>0){
            for(int i = 0 ;i < h ; i++){
                headA = headA.next;
            }
            while(headA!=null&&headB!=null){
                if(headA==headB){
                    return headA;
                }else{
                    headA = headA.next;
                    headB = headB.next;
                }
            }
        }else if(h<0){
            h = Math.abs(h);
            for(int i = 0 ;i < h ; i++){
                headB = headB.next;
            }
            while(headA!=null&&headB!=null){
                if(headA==headB){
                    return headB;
                }else{
                    headA = headA.next;
                    headB = headB.next;
                }
            }
        }else{
            while(headA!=null&&headB!=null){
                if(headA==headB){
                    return headB;
                }else{
                    headA = headA.next;
                    headB = headB.next;
                }
            }
        }
        return null;
    }
}