黄山地区建设行业网站,网站定向推送怎么做,个人网站开发的意义,如何做网站建设方案链表相交
题目#xff1a;面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点#xff0c;返回 null 。
图示两个链表在节点 c1 开始相交**#xff1a;** 题目数据 保证 整个链式结…链表相交
题目面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null 。
图示两个链表在节点 c1 开始相交**** 题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
示例 1 输入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 中节点数目为 mlistB 中节点数目为 n0 m, n 3 * 1041 Node.val 1050 skipA m0 skipB n如果 listA 和 listB 没有交点intersectVal 为 0如果 listA 和 listB 有交点intersectVal listA[skipA 1] listB[skipB 1]
**进阶**你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案
方法一
使用暴力遍历。
// 暴力
func getIntersectionNode(headA, headB *ListNode) *ListNode {for headA ! nil {p : headBfor p ! nil {if p headA {return p}p p.Next}headA headA.Next}return nil
}时间复杂度O(n²)空间复杂度为O(1)
方法二
将链表转数组反向遍历寻找第一个不等节点的后续。
// 转数组
func getIntersectionNode(headA, headB *ListNode) *ListNode {A : make([]*ListNode, 0)B : make([]*ListNode, 0)for headA ! nil {A append(A, headA)headA headA.Next}for headB ! nil {B append(B, headB)headB headB.Next}al : len(A) - 1bl : len(B) - 1for al 0 bl 0 {if A[al] ! B[bl] {break}al--bl--}if al len(A)-1 || bl len(B)-1 {return nil} else {return A[al1]}
}时间复杂度为O(mn)但空间复杂度也为O(mn)。
方法三
详解代码随想录 (programmercarl.com)
简单来说就是先获取长度再将长的链表修改为和短链表一样长最后齐步走找到相等的节点。
// 齐步走
func getIntersectionNode(headA, headB *ListNode) *ListNode {pa : headApb : headBal : 0bl : 0for pa ! nil {pa pa.Nextal}for pb ! nil {pb pb.Nextbl}if al bl {for al ! bl {headA headA.Nextal--}} else {for al ! bl {headB headB.Nextbl--}}for headA ! headB {headA headA.NextheadB headB.Next}return headA
}时间复杂度为O(mn)空间复杂度O(1)
