• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

快慢指针查找入环点

成环一定相遇证明

假设环上有N节点,快指针快和慢指针慢从环上任意两点开始。只要N有限,总有快超过慢的时候,那么快超过慢之前有两种情况:

快慢前一个,此时快在m 1的位置,慢在m 2的位置。在接下来的练习中,快和慢都将移动到m 3的位置,而快和慢都是相遇.

快慢前两次,快在m,慢在m 2,下一次,快在m 2,慢在m 3,就回到情况1,快和慢还在相遇.

因此,可以断定,Fast 第一次追上 Slow 的时候就会与 Slow 相遇,不会超过 Slow;

这个方法可以用来证明链表上是否有环:

func has cycle(head * ListNode)bool {

if head==nil || head。Next==nil {

返回false

}

fastNode,lowNode :=头,头

为了fastNode!=nil fastNode。下一个!=零{

低节点=低节点。然后

fastNode=fastNode。下一个,下一个

if lowNode==fastNode {

返回true

}

}

返回false

}

入环节点查找

慢进擂台有两种情况:

假设当慢进入拳击台时遇到了快。这时,Fast已经跑完了环上的n(n=1)圈。此时,假设在进入环之前,环上有a节点和b节点。众所周知,快速运动的长度必须是慢速运动的两倍。可以知道:2a=a nb可以导出a=nb b .此时,如果来自交汇点的指针与来自链表头的指针以相同的速度移动,那么它就一定在入环的节点相遇.

假设入环时慢未遇快,入环前有a节点。因为此时快在慢的前面,慢会在入圈后跑一圈前遇到快。假设此时慢速运行b节点,其距离进入环的点有5个节点。这时,Fast已经跑完了环上的c圈加n(n=1)节点。此时有2(a b)=a n(b c) b,换算后有a=(n-1)(b c) c。因为C是剩余的节点,正好A是剩余的b加上整数个环长,会和指针从链表头开始移动的速度一样,所以肯定会在c;

在这两种情况下,它们都会在环入口点相遇,因此可以证明这种方法可以用来寻找环入口点:

func detect cycle(head * ListNode)* ListNode {

如果head==nil {

返回零

}

intersect :=getIntersect(head)

if intersect==nil {

返回零

}

ptr1 :=头

ptr2 :=相交

对于ptr1!=ptr2 {

ptr1=ptr1。然后

ptr2=ptr2。然后

}

返回ptr1

}

func getIntersect(head * ListNode)* ListNode {

if head==nil || head。Next==nil {

返回零

}

fastNode,lowNode :=头,头

为了fastNode!=nil fastNode。下一个!=零{

低节点=低节点。然后

fastNode=fastNode。下一个,下一个

if lowNode==fastNode {

返回快速节点

}

}

返回零

}

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now