当前位置:网站首页>LC interview question 02.07 Linked list intersection & lc142 Circular linked list II
LC interview question 02.07 Linked list intersection & lc142 Circular linked list II
2022-07-07 07:05:00 【Jane_ one hundred and sixty-three】
Interview questions 02.07. The list intersects
thought : Find the linked list A length , Linked list B length , Get AB The difference in length . If A Long , So let's A Go ahead , Go to the AB Length difference , Finally, we will meet at the intersection .
notes : picture source - Random code recording
Code :
# 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. Circular list II
Q1: Judge whether there is a ring
Q2: Judge the position of the ring inlet ?
notes : picture source - Random code recording
Set up :fast Two steps at a time ,slow One step at a time . If there is a ring ,fast It must be better than slow Enter the ring first , Finally, it must meet in the ring .
When we met ,fast The journey x+y+n(y+z) ,slow The journey x+y,fast Speed is slow Of 2 times
Then we can get the formula :x+y+n(y+z) = 2(x+y)
Simplify to get :x = (n-1)(y+z)+z What does that mean ? Two nodes ab Same speed , A node a Start from the beginning , Another node b Start from where you meet , Eventually, they will meet at the ring entry node . It's just b Maybe it's in the ring 0 Circle or (n-1) Circle problem .
The code is as follows :
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast, slow = head, head
cur = head
# If it is empty , Then there is no ring
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# fast==slow, here fast and slow Both point to the encounter node
if fast == slow:
while slow != cur:
slow = slow.next
cur = cur.next
return cur
# cur == slow, Meet at the ring entrance ,index It is the index of the ring entry
return None
Q3: What to ask fast and slow When we met ,slow It must be gone x+y, instead of x+y+n(y+z)
First slow When entering the ring ,fast It must have entered the ring . If slow Ring entry ,fast Also at the ring entrance , Then expand the ring into a straight line , It must be at the ring entrance 3 Meeting place .
But the actual :slow When entering the ring ,fast It must be somewhere in the ring , As shown in the figure below . Then it means in fast Go to the ring entrance 3 When , go k+n,slow go (k+n)/2<n, It means that slow Did not go to the ring mouth 3, So they are in Huankou 2- Ring mouth 3 On the way to meet , That is to say slow The link in Kaishi has been connected with fast Met .
Then a classmate said again , Why? fast Can't skip ? I have just said it once ,fast be relative to slow Is to move one node at a time , So it's impossible to jump over .
Reference link
[1] Random code recording 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
边栏推荐
猜你喜欢
随机推荐
How to share the same storage among multiple kubernetes clusters
CompletableFuture使用详解
.net 5 FluentFTP连接FTP失败问题:This operation is only allowed using a successfully authenticated context
2018年江苏省职业院校技能大赛高职组“信息安全管理与评估”赛项任务书
ESXI挂载移动(机械)硬盘详细教程
The latest trends of data asset management and data security at home and abroad
7天零基础能考证HCIA吗?华为认证系统学习路线分享
oracle如何备份索引
Big coffee gathering | nextarch foundation cloud development meetup is coming
LVS+Keepalived(DR模式)学习笔记
RuntimeError: CUDA error: CUBLAS_STATUS_ALLOC_FAILED when calling `cublasCreate(handle)`问题解决
非父子组件的通信
.net core 访问不常见的静态文件类型(MIME 类型)
Can 7-day zero foundation prove HCIA? Huawei certification system learning path sharing
MATLAB小技巧(29)多项式拟合 plotfit
根据IP获取地市
2022/07/04学习记录
Network foundation - header, encapsulation and unpacking
MySQL user permissions
MySQL view bin log and recover data