leetcode160:相交链表

/**
      *题目：
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
     * 如果两个链表不存在相交节点，返回 null 。
     * 注意，函数返回结果后，链表必须 保持其原始结构
     * @param headA
     * @param headB
     * @return
     * 思路：
     * 1. 使用hash结构的元素不重复特点
     * 2. 首先将一个链表中所有节点全部存储到hashset集合中
     * 3. 然后遍历另一条链表，在遍历的同时判断当前节点是否在hash集合中
     * 4. 若在，则说明相交，返回当前节点即可
     * 5. 若不在，则说明没有重复节点，返回空
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //定义hash集合保存链表A中所有节点
        HashSet<ListNode> visited = new HashSet<>();
        //定义辅助指针指向头节点
        ListNode temp = headA;
        //因为链表结构不能改变，使用辅助指针遍历整个链表
        while (temp != null){
            visited.add(temp);
            temp = temp.next;
        }
        //将辅助指针指向链表B
        temp = headB;
        //遍历链表B并判断是否相交
        while (temp != null){
            if (visited.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }