Leetcode刷题100天—160. 相交链表(哈希表)—day10

落日映苍穹つ 2022-09-10 04:19 134阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210904153349543][]

#### [160. 相交链表][160.] ####

难度简单1336收藏分享切换为英文接收动态反馈

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

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

[![img][]][img 1]

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

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

**示例 1：**

[![img][img 2]][img_img 2]

输入：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：**

[![img][img 3]][img_img 3]

输入：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：**

[![img][img 4]][img_img 4]

输入：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]`

\*\*进阶：\*\*你能否设计一个时间复杂度 `O(n)` 、仅用 `O(1)` 内存的解决方案？

package 哈希表;
    
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Set;
    
    /* * 1 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/ */
    public class _160_相交链表 { 
    // 通过哈希集合解决题目
    	public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
    // 设置哈希集合
    		Set<ListNode> res=new HashSet<ListNode>();
    // 设置头节点
    		ListNode node=headA;
    // while循环将节点存入集合中
    		while(node!=null) { 
    			res.add(node);
    			node=node.next;
    		}
    // 通过循环headB查看是否有值在集合中，如果有就直接返回
    		node=headB;
    		while(node!=null) { 
    			if (res.contains(node)) { 
    				return node;
    			}
    			node=node.next;
    		}
    //如果没有相交的值就返回null
    		return null;
    		
    	}	
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210904153349543]: /images/20220829/75359c25fbd24b159680548b6eb07ca7.png
[160.]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
[img]: /images/20220829/6645091711a948ed9e96f44d496a5d4e.png
[img 1]: https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png
[img 2]: https://img-blog.csdnimg.cn/img_convert/ae6d8589871f13c05f80d247fc7f842e.png
[img_img 2]: https://assets.leetcode.com/uploads/2018/12/13/160_example_1.png
[img 3]: https://img-blog.csdnimg.cn/img_convert/6bba6ee050d87974cf8d47c34f7d454d.png
[img_img 3]: https://assets.leetcode.com/uploads/2018/12/13/160_example_2.png
[img 4]: https://img-blog.csdnimg.cn/img_convert/0dede36b1b22b3304429b96d722cc282.png
[img_img 4]: https://assets.leetcode.com/uploads/2018/12/13/160_example_3.png