网站推广类型,微商系统软件开发,湛江市企业网站seo点击软件,公司注册信息查询文章目录 1.问题描述2.难度等级3.热门指数4.解题思路方法一#xff1a;暴力法方法二#xff1a;哈希表方法三#xff1a;双栈方法四#xff1a;双指针#xff1a;记录链表长度方法五#xff1a;双指针#xff1a;互换遍历 5.实现示例参考文献 1.问题描述
给两个单链表的… 文章目录 1.问题描述2.难度等级3.热门指数4.解题思路方法一暴力法方法二哈希表方法三双栈方法四双指针记录链表长度方法五双指针互换遍历 5.实现示例参考文献 1.问题描述
给两个单链表的头节点 headA 和 headB 请找出并返回两个单链表相交的起始节点。如果不存在相交节点返回 null 。
题目数据保证整个链式结构中不存在环。
注意函数返回结果后链表必须保持其原始结构。
示例 1 相交返回结点 8。
示例 2 相交返回结点 2。
示例 3 不相交返回 null。
进阶 你能否设计一个时间复杂度 O(m n) 、仅用 O(1) 内存的解决方案
2.难度等级
Easy。
3.热门指数
★★★★★
出题公司阿里、腾讯、字节。
4.解题思路
解这道题之前我们需要首先明确一个概念何为相交
相交指的是结点为同一个结点那么指向结点的指针是相同的而不是第一个结点值相同。
如果不考虑时间和空间复杂度那么有多种解法。
假设 m 和 n 是分别是链表 headA 和 headB 的长度。
方法一暴力法
从头开始遍历第一个链表遍历第一个链表的每个节点时同时从头到尾遍历第二个链表看是否有相同的节点第一次找到相同的节点即第一个交点。
若第一个链表遍历结束后还未找到相同的节点即不存在交点。
时间复杂度 O ( n 2 ) O(n^2) O(n2)。
空间复杂度 O ( 1 ) O(1) O(1)。
方法二哈希表
判断两个链表是否相交可以使用哈希集合存储链表节点。
首先遍历链表 headA将链表中的每个节点加入哈希表中。然后遍历链表 headB判断节点是否在哈希表中。
如果链表 headB 中的所有节点都不在哈希集合中则两个链表不相交返回 null。
时间复杂度 O(mn)需要遍历两个链表各一次。
空间复杂度 O(m)需要使用哈希表存储链表 headA 的全部节点。
方法三双栈
我们可以从头遍历两个链表。创建两个栈第一个栈存储第一个链表的节点第二个栈存储第二个链表的节点。每遍历到一个节点时就将该节点入栈。两个链表都入栈结束后。
则通过判断栈顶的节点是否相等即可判断两个单链表是否相交。因为我们知道若两个链表相交则从第一个相交节点开始后面的节点都相交。
若两链表相交则循环出栈直到遇到两个出栈的节点不相同则这个节点的后一个节点就是第一个相交的节点。
时间复杂度 O(mn)。需要遍历两个链表各两次一次是入栈一次是出栈。
空间复杂度 O(mn)需要使用两个栈存储链表 headA 和 headB 的所有结点。
方法四双指针记录链表长度
同时遍历两个链表到尾部同时记录两个链表的长度。若两个链表最后的一个节点相同则两个链表相交。
有两个链表的长度后我们就可以知道哪个链表长设较长的链表长度为 len1短的链表长度为 len2。
则先让较长的链表向后移动 len1-len2 个长度。然后开始从当前位置同时遍历两个链表当遍历到的链表的节点相同时则这个节点就是第一个相交的节点。
时间复杂度 O ( m n ) O(mn) O(mn)两个指针同时遍历两个链表然后再遍历两个链表至相同结点。
空间复杂度 O ( 1 ) O(1) O(1)。
方法五双指针互换遍历
当链表 headA 和 headB 都不为空时创建两个指针 pA 和 pB初始时分别指向两个链表的头节点 headA 和 headB然后将两个指针依次遍历两个链表的每个节点。具体做法如下 每步操作需要同时更新指针 pA 和 pB。 如果指针 pA 不为空则将指针 pA 移到下一个节点如果指针 pB 不为空则将指针 pB 移到下一个节点。 如果指针 pA 为空则将指针 pA 移到链表 headB 的头节点如果指针 pB 为空则将指针 pB 移到链表 headA 的头节点。 当指针 pA 和 pB 指向同一个节点或者都为空时返回它们指向的节点或者 null。
为什么第一次遍历完后互换从头遍历后如果相交会同时到达相交结点呢
假设下面是一个相交的两个链表省去了结点。其中链表 headA 的长度为 a c m链表 headB 的长度为 b c n。 因为 a c b 等于 b c a所以第一次遍历完后互换从头遍历会同时到达相交结点。
如果两个链表不相交也会同时到达尾结点因为 m n 等于 n m。
时间复杂度 O ( m n ) O(mn) O(mn)两个指针同时遍历两个链表然后再遍历两个链表至相同结点。
空间复杂度 O ( 1 ) O(1) O(1)。
5.实现示例
面以 Golang 为例给出「双指针互换遍历」的实现。
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {pA, pB : headA, headBfor pA ! nil || pB ! nil {if pA pB {return pA}if pA nil {pA headB} else {pA pA.Next}if pB nil {pB headA} else {pB pB.Next} }return nil
}参考文献
160. 相交链表 - LeetCode 判断两个单链表是否相交及找到第一个交点原创 -CSDN
