Leetcode 160. 相交链表(哈希YYDS)

﹏ヽ暗。殇╰゛Y 2022-10-18 12:42 114阅读 0赞

#### 题目重述 ####

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

#### 示例 1： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]

输入：intersectVal = 8, listA = \[4,1,8,4,5\], listB = \[5,0,1,8,4,5\], skipA = 2, skipB = 3  
输出：Intersected at ‘8’  
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。  
从各自的表头开始算起，链表 A 为 \[4,1,8,4,5\]，链表 B 为 \[5,0,1,8,4,5\]。  
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

#### 示例 2： ####

输入：intersectVal = 2, listA = \[0,9,1,2,4\], listB = \[3,2,4\], skipA = 3, skipB = 1  
输出：Intersected at ‘2’  
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。  
从各自的表头开始算起，链表 A 为 \[0,9,1,2,4\]，链表 B 为 \[3,2,4\]。  
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

#### 示例 3： ####

输入：intersectVal = 0, listA = \[2,6,4\], listB = \[1,5\], skipA = 3, skipB = 2  
输出：null  
解释：从各自的表头开始算起，链表 A 为 \[2,6,4\]，链表 B 为 \[1,5\]。  
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。  
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m  
listB 中节点数目为 n  
0 <= m, n <= 3 \* 104  
1 <= Node.val <= 105  
0 <= skipA <= m  
0 <= skipB <= n  
如果 listA 和 listB 没有交点，intersectVal 为 0  
如果 listA 和 listB 有交点，intersectVal == listA\[skipA + 1\] == listB\[skipB + 1\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

利用hash，第一次遍历链表A所有结点，存入hash表，之后遍历B链表所有节点，如果有重复的，说明相交。

这里我的key直接就是ListNode，用Hashmap用的比较习惯，其实也可以直接用`<Set>`

#### Java ####

public class Solution {
        
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            Map<ListNode,Integer> m = new HashMap<>();
            ListNode p = headA,q = headB;
            while (p!=null)
            {
        
                m.put(p,p.val);
                p = p.next;
            }
            while(q!=null)
            {
        
                if(m.containsKey(q))
                {
        
                    return q;
                }
                q = q.next;
            }
            return null;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]: /images/20221005/c6b5aad3ccc24859b97020e49f0991b6.png