当前位置:网站首页>LC 面试题 02.07. 链表相交 & LC142. 环形链表II
LC 面试题 02.07. 链表相交 & LC142. 环形链表II
2022-07-07 03:09:00 【Jane_163】
面试题 02.07. 链表相交
思想:找到链表A长度,链表B长度,求得AB长度的差值。如果A长,那么让A先走,走到AB长度差值处,最后一定会在交点处相遇。
注:图片来源- 代码随想录
代码:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
def action(lengthA, lengthB, nodeA, nodeB):
length = lengthA - lengthB
for i in range(length):
nodeA = nodeA.next
print("nodeA.val",nodeA.val)
while nodeA and nodeB:
if nodeA == nodeB:
print(nodeA.val)
return nodeA
nodeA = nodeA.next
nodeB = nodeB.next
return None
if not headA or not headB:
return None
lengthA, lengthB = 0, 0
nodeA, nodeB = headA, headB
while nodeA:
nodeA = nodeA.next
lengthA += 1
while nodeB:
nodeB = nodeB.next
lengthB += 1
print("lengthA", lengthA)
print("lengthB", lengthB)
nodeA, nodeB = headA, headB
if lengthA > lengthB:
return action(lengthA, lengthB, nodeA, nodeB)
else:
return action(lengthB, lengthA, nodeB, nodeA)
LC142. 环形链表II
Q1:判断是否有环
Q2:判断环入口位置?
注:图片来源- 代码随想录
设定:fast指针每次走两步,slow指针每次走一步。若有环,fast一定是比slow先进入环的,最终一定是在环中相遇的。
相遇时,fast走过的路程 x+y+n(y+z) ,slow走过的路程 x+y,fast速度为slow的2倍
则可以得到公式:x+y+n(y+z) = 2(x+y)
化简得到:x = (n-1)(y+z)+z 这代表什么意思呢? 两个节点ab同速度,一节点a从头结点出发,另一节点b从相遇处出发,最终一定会在环形入口节点相遇。只不过b可能是在环里转了0圈或者(n-1)圈的问题。
代码如下:
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast, slow = head, head
cur = head
# 若为空,则不存在环
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# fast==slow,此时fast和slow均指向相遇节点
if fast == slow:
while slow != cur:
slow = slow.next
cur = cur.next
return cur
# cur == slow,在环入口相遇,index即为环入口的索引
return None
Q3:问什么fast和slow相遇时,slow一定是走了 x+y,而不是 x+y+n(y+z)
首先slow进入环的时候,fast一定也进入环了。如果slow进环,fast也在环入口,那么将环展开成直线,一定会在环入口3处相遇。
但是实际:slow进入环的时候,fast一定在环的某个位置,如下图所示。那么就意味着在fast走到环入口3的时候,走了k+n,slow走了(k+n)/2<n,那么说明slow没走到环口3,所以他们在环口2-环口3的路上就相遇了,也就是slow在开视走的那一环已经和fast相遇了。
那有同学又说了,为什么fast不能跳过去呢? 在刚刚已经说过一次了,fast相对于slow是一次移动一个节点,所以不可能跳过去。
参考链接
[1] 代码随想录 https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html#%E6%80%9D%E8%B7%AF
边栏推荐
猜你喜欢
企业如何进行数据治理?分享数据治理4个方面的经验总结
Abnova循环肿瘤DNA丨全血分离,基因组DNA萃取分析
Abnova 体外转录 mRNA工作流程和加帽方法介绍
Stack and queue-p79-10 [2014 unified examination real question]
[start from scratch] detailed process of deploying yolov5 in win10 system (CPU, no GPU)
循环肿瘤细胞——Abnova 解决方案来啦
使用TCP/IP四层模型进行网络传输的基本流程
大促过后,销量与流量兼具,是否真的高枕无忧?
带你刷(牛客网)C语言百题(第一天)
7天零基础能考证HCIA吗?华为认证系统学习路线分享
随机推荐
Redhat5 installing vmware tools under virtual machine
Get the city according to IP
什么情况下考虑分库分表
SolidWorks GB Library (steel profile library, including aluminum profile, aluminum tube and other structures) installation and use tutorial (generating aluminum profile as an example)
jdbc数据库连接池使用问题
Distributed ID solution
途家、木鸟、美团……民宿暑期战事将起
场馆怎么做体育培训?
请教一下,监听pgsql ,怎样可以监听多个schema和table
Apache ab 压力测试
SVN version management in use replacement release and connection reset
JESD204B时钟网络
Postgresql中procedure支持事务语法(实例&分析)
Matlab tips (29) polynomial fitting plotfit
Postgresql源码(59)分析事务ID分配、溢出判断方法
JWT certification
MySQL installation
多个kubernetes集群如何实现共享同一个存储
【解决】Final app status- UNDEFINED, exitCode- 16
MOS tube parameters μ A method of Cox