网站建设4038gzs,橱柜网站源码,网站面包屑导航设计特点,qq浏览器小程序入口相交链表题目描述
给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交#xff1a; 题目数据 保证 整个链式结构中不存在环。
注意#xff0…相交链表题目描述
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
自定义评测 评测系统 的输入如下你设计的程序 不适用 此输入
intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0 listA - 第一个链表 listB - 第二个链表 skipA - 在 listA 中从头节点开始跳到交叉节点的节点数 skipB - 在 listB 中从头节点开始跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案 。
题解
方法一哈希集合
判断两个链表是否相交可以使用哈希集合存储链表节点。
首先遍历链表 headA并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB对于遍历到的每个节点判断该节点是否在哈希集合中
如果当前节点不在哈希集合中则继续遍历下一个节点
如果当前节点在哈希集合中则后面的节点都在哈希集合中即从当前节点开始的所有节点都在两个链表的相交部分因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点返回该节点。
如果链表 headB 中的所有节点都不在哈希集合中则两个链表不相交返回 null。
// 定义哈希表结构体
struct HashTable {struct ListNode *key; // 哈希表的键指向链表节点UT_hash_handle hh; // 哈希表的特殊域用于管理哈希表
};// 函数获取两个链表的交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {// 初始化哈希表struct HashTable *hashTable NULL;// 遍历链表 headA将节点添加到哈希表中struct ListNode *temp headA;while (temp ! NULL) {// 临时指针struct HashTable *tmp;// 在哈希表中查找当前节点是否存在HASH_FIND(hh, hashTable, temp, sizeof(struct HashTable *), tmp);// 如果节点不存在于哈希表中则将其加入哈希表if (tmp NULL) {tmp malloc(sizeof(struct HashTable));tmp-key temp;HASH_ADD(hh, hashTable, key, sizeof(struct HashTable *), tmp);}// 继续遍历下一个节点temp temp-next;}// 遍历链表 headB查找是否存在于哈希表中的节点temp headB;while (temp ! NULL) {// 临时指针struct HashTable *tmp;// 在哈希表中查找当前节点是否存在HASH_FIND(hh, hashTable, temp, sizeof(struct HashTable *), tmp);// 如果找到了交点则直接返回该节点if (tmp ! NULL) {return temp;}// 继续遍历下一个节点temp temp-next;}// 如果遍历完链表 headB 都没有找到交点则返回 NULLreturn NULL;// 这种方法利用了哈希表的快速查找特性将时间复杂度从线性降低到了接近常数级别。// 总体而言这段代码展示了哈希表在解决链表相关问题中的应用特别是在寻找交点等场景下能够提供高效的解决方案。
}
哈希表
哈希表Hash Table也称为散列表是一种常用的数据结构用于实现关联数组。它通过将键key映射到数组Array的特定位置来实现快速的数据检索。哈希表的主要思想是利用哈希函数将键转换为数组索引然后将值存储在该索引位置的数组中。
哈希表的基本结构包括以下几个重要组成部分 哈希函数Hash Function哈希函数是哈希表的核心它负责将键映射到数组的特定位置。良好的哈希函数应该具有以下特性 易于计算哈希函数应该能够快速计算出哈希值。均匀分布哈希函数应该能够将键均匀地分布在数组中以减少冲突的发生。最小冲突哈希函数应该能够尽量减少键的冲突即不同的键映射到相同的数组索引的情况。 数组Array哈希表使用数组来存储键值对。每个数组位置称为“桶”Bucket一个桶可以存储一个或多个键值对。当发生哈希冲突时通常使用一种解决冲突的方法来处理比如链地址法或开放地址法。 解决冲突的方法由于不同的键可能会映射到相同的数组索引位置所以哈希表需要一种解决冲突的方法。常见的方法包括 链地址法Chaining将具有相同哈希值的键值对存储在同一个桶中的链表或其他数据结构中。开放地址法Open Addressing当发生冲突时通过探查数组中的其他位置来寻找空闲的位置并将键值对插入到空闲位置中。
哈希表的时间复杂度取决于哈希函数的性能和冲突解决方法的效率。在理想情况下哈希表可以实现常数时间复杂度的查找、插入和删除操作O(1)但在最坏情况下可能会退化到线性时间复杂度O(n)。
哈希表被广泛应用于各种编程语言的标准库中用于实现诸如字典Dictionary、集合Set等数据结构以及在数据库中用于加快数据检索速度等场景。
方法二双指针
思路和算法
使用双指针的方法可以将空间复杂度降至 O(1)。
只有当链表 headA 和 headB 都不为空时两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空如果其中至少有一个链表为空则两个链表一定不相交返回 null。
当链表 headA 和 headB 都不为空时创建两个指针 pA 和 pB初始时分别指向两个链表的头节点 headA 和 headB然后将两个指针依次遍历两个链表的每个节点。具体做法如下
每步操作需要同时更新指针 pA 和 pB。
如果指针 pA 不为空则将指针 pA 移到下一个节点如果指针 pB 不为空则将指针 pB 移到下一个节点。
如果指针 pA 为空则将指针 pA 移到链表 headB 的头节点如果指针 pB 为空则将指针 pB 移到链表 headA 的头节点。
当指针 pA 和 pB 指向同一个节点或者都为空时返回它们指向的节点或者 null。
证明
下面提供双指针方法的正确性证明。考虑两种情况第一种情况是两个链表相交第二种情况是两个链表不相交。
情况一两个链表相交
链表headA 和 headB 的长度分别是 m 和 n。假设链表 headA 的不相交部分有 a 个节点链表 headB 的不相交部分有 b 个节点两个链表相交的部分有 c 个节点则有 acmbcn。
如果 ab则两个指针会同时到达两个链表相交的节点此时返回相交的节点
如果 a≠b则指针 pA 会遍历完链表 headA指针 pB 会遍历完链表 headB两个指针不会同时到达链表的尾节点然后指针 pA 移到链表 headB 的头节点指针 pB 移到链表 headA 的头节点然后两个指针继续移动在指针 pA 移动了 acb 次、指针 pB 移动了 bca 次之后两个指针会同时到达两个链表相交的节点该节点也是两个指针第一次同时指向的节点此时返回相交的节点。
情况二两个链表不相交
链表 headA 和 headB 的长度分别是 m 和 n。考虑当 mn 和 m≠n 时两个指针分别会如何移动
如果 mn则两个指针会同时到达两个链表的尾节点然后同时变成空值 null此时返回 null
如果 m≠n则由于两个链表没有公共节点两个指针也不会同时到达两个链表的尾节点因此两个指针都会遍历完两个链表在指针 pA 移动了 mn 次、指针 pB 移动了 nm 次之后两个指针会同时变成空值 null此时返回 null。
// 函数获取两个链表的交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {// 如果其中一个链表为空则直接返回 NULL因为没有交点if (headA NULL || headB NULL) {return NULL;}// 初始化两个指针 pA 和 pB 分别指向链表 headA 和 headB 的头节点struct ListNode *pA headA, *pB headB;// 当 pA 不等于 pB 时循环即两个指针没有相遇while (pA ! pB) {// 如果 pA 到达了链表 headA 的末尾则将 pA 指向链表 headB 的头节点pA pA NULL ? headB : pA-next;// 如果 pB 到达了链表 headB 的末尾则将 pB 指向链表 headA 的头节点pB pB NULL ? headA : pB-next;}// 返回 pA或 pB即两个链表的交点如果没有交点则返回 NULLreturn pA;
}
帮助理解
将2个链表在末尾加上对方碰到第一个相同的点要么是交点要么是末尾
situation 1
A: 1 - 2 - 3 - C - 4 - 5 - null
B: 6 - 7 - C - 4 - 5 - null
A B: 1 - 2 - 3 - C - 4 - 5 - 6 - 7 - C - 4 - 5 - null
B A: 6 - 7 - C - 4 - 5 - 1 - 2 - 3 - C - 4 - 5 - null
situation 2
A: 1 - 2 - 3 - 4 - 5 - null
B: 6 - 7 - 8 - 3 - null
A B: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 3 - null
B A: 6 - 7 - 8 - 3 - 1 - 2 - 3 - 4 - 5 - null
作者力扣官方题解 链接https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/811625/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
