关于链表有环的扩展问题：求环的长度和入环节点

一、求环的长度
二、求入环节点

一、求环的长度

解法：当两个指针首次相遇，说明链表有环，让两个指针从相遇点继续循环前进，并统计前进的次数，直到两个指针再次相遇。具体可参考如下公式：
环长=每一次速度差 X 前进次数

代码实现：

class Node:
def __init__(self,data):
self.data=data
self.next=None
def isCycle(head):
p1=head
p2=head
flag=False
while p1 is not None and p2.next is not None:
p1=p1.next
p2=p2.next.next
if p1==p2:
print('链表有环')
flag=True
break
step=0
if flag:
while p1 is not None and p2.next is not None:
p1=p1.next
p2=p2.next.next
step += 1
if p1==p2:
break
cycleLength=(2-1)*step # 环长=每一次速度差 X 前进次数
return step
node1=Node(4)
node2=Node(3)
node3=Node(5)
node4=Node(1)
node5=Node(8)
node1.next=node2
node2.next=node3
node3.next=node4
node4.next=node5
node5.next=node2
print('环的长度为：',isCycle(node1))

二、求入环节点

解法：先看一张图

假设从链表头节点到入环点的距离是D，从入环点到首次相遇点的距离是S1，从首次相遇点回到入环点的距离是S2，那么：
p1指针一次只走一步，所以走的距离是D+S1
p2指针一次走两步，多走了n(n>=1)整圈，所以走的距离是D+S1+n(S1+S2)
由于p2的速度是p1的2倍，所以所走距离也是p1的二倍，因此有下列等式：
2(D+S1)=D+S1+n(S1+S2)
也就是说：从链表头节点到入环点的距离，等于从首次相遇点绕环n-1圈再回到入环点的距离。
所以：
只要把其中一个指针放回到头节点位置，另一个指针保持在首次相遇点，两个指针都是每次向前走1步，那么，它们最终相遇的节点就是入环节点。

也就是说：从首次相遇点开始，保持一个指针不动，另一个指针指向头节点，然后两个指针同步前进，它们再次相遇的节点就是入环节点。

代码实现：

class Node:
def __init__(self,data):
self.data=data
self.next=None
def isCycle(head):
p1=head
p2=head
flag=False
while p1 is not None and p2.next is not None:
p1=p1.next
p2=p2.next.next
if p1==p2:
print('链表有环')
flag=True
break
p1=head
while p1 is not None and p2.next is not None:
p1=p1.next
p2=p2.next
if p1==p2:
print('入环点是：',p1.data)
break
node1=Node(4)
node2=Node(3)
node3=Node(5)
node4=Node(1)
node5=Node(8)
node1.next=node2
node2.next=node3
node3.next=node4
node4.next=node5
node5.next=node2
isCycle(node1)

最后

以上就是怕孤单红酒为你收集整理的关于链表有环的扩展问题：求环的长度和入环节点的全部内容，希望文章能够帮你解决关于链表有环的扩展问题：求环的长度和入环节点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。