160.相交链表（简单）

最简单的方法

直接使用hashSet存储ListNode即可。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> hset = new HashSet<>();
        ListNode startA = headA;
        ListNode startB = headB;
        while(startA != null){
            hset.add(startA);
            startA = startA.next;
        }

        while(startB != null){
            if(hset.contains(startB)){
                return startB;
            }
            startB = startB.next;
        }
        return null;
    }
}

大佬的解法

利用两个指针，分别跑headA+headB的长度，两边重合的点就可以相交的节点值

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
        定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
        两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
        **/
        if(headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
        while(pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}