视频发布播放网站建设,光环时讯网站,驻马店北京网站建设,怎么建网站做这里写目录标题 一、LCR 023. 相交链表二、142. 环形链表 II 一、LCR 023. 相交链表
给定两个单链表的头节点 headA 和 headB #xff0c;请找出并返回两个单链表相交的起始节点。如果两个链表没有交点#xff0c;返回 null 。 提示#xff1a;
listA 中节点数目为 m list… 这里写目录标题 一、LCR 023. 相交链表二、142. 环形链表 II 一、LCR 023. 相交链表
给定两个单链表的头节点 headA 和 headB 请找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 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) 内存的解决方案
分析 这道题比较容易想到的是创建一个hash表然后循环依次A将A的所有节点添加至Hash表中。 再循环依次B每次判断B的当前节点是否在hash表中。 代码如下
class Solution:def getIntersectionNode(self,headA,headB):d{}while headA:d[headA]headAheadAheadA.nextwhile headB:if d.get(headB):return headBheadBheadB.next()return None
这样的思路可以通过但是题目说了程序尽量满足 O(n) 时间复杂度且仅用 O(1) 内存。 hash表构造了额外的O(n)空间复杂度那么如何来实现使用O(1)的时间复杂度完成呢
思路 假设相交前A链表的长度为x,B链表的长度为z 两个链表相交的点为图中的w 相交后共同的长度为y。 我们分别创建p1、p2两个指针指向A、B 当p1或者p2走到头时则将指针重新指向另外的一个链表。 当p1、p2相等时终止返回p1或p2就是第一个相交节点。 因为p1、p2走过的路程都是xyz class ListNode:def __init__(self, x):self.val xself.next Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode:node_a headAnode_b headBwhile node_a or node_b:if node_a node_b:return node_aif node_a:node_a node_a.nextelse:node_a headBif node_b:node_b node_b.nextelse:node_b headAreturn二、142. 环形链表 II
中等
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 思路使用双指针法解决 本题的求解过程中双指针会产生两次相遇 双指针的第一次相遇 设两指针fastslow指向链表头部head 令fast每轮走2步slow每轮走 1步 执行以上两步后可能出现两种结果
第一种结果fast指针走过链表末端说明链表无环此时直接返回null 如果链表存在环则双指针一定会相遇。因为每走1轮fast与slow的间距1fast一定会追上slow。
当fast slow时当双指针相遇时快指针重新指向链表头部节点slow和fast同时每轮向前走1步。 当fast指针走到fa步时slow指针走到sab步此时两个指针重合并且同时指向链表环入口返回slow指向的节点即可。
class Solution1:def detectCycle(self, head):fast, slow head, headwhile True:if not fast and not fast.next:returnfastfast.next.nextslowslow.nextif fast slow:breakfast headwhile fast ! slow:fast, slow fast.next, slow.nextreturn fast
解题思路步骤
