lintcode 103. 带环链表 II

楚天乐 905 3 条

首先,判断是否有环;接着计算环中有多少个节点;再第一步得到的节点倒推,直到有一个不相同,他的后继节点就是环的起始节点。

第一步,很简单,设置两个指针A和B,指向头结点。A和B分别以速度1和2前进,如果A和B相遇,则说明有环(B追上A)
退出条件:

A == B, B追上A,设置当前节点为SomeWhereInRing, 跳去第二步
B == None or B.next == None, 到达链表结尾。 此时算法可以结束了,返回None
第二步,计算环中有几个节点
设置counter = 1, A = SomeWhereInRing, 循环绕环一圈即可知道环中有多少节点
while A != SomeWhereInRing:
counter += 1
A = A.next

第三步,以SomeWhereInRing为基准向前倒推,直到能推出两个节点A != B。

单链表无法得到前驱节点,所以我们要想得到SomeWhereInRing的前驱节点,只能通过两种方式:

我们直到SomeWhereInRing节点相对于head头结点的距离,M
我们直到环中有N个节点
那么我们设置指针A和B,A指向head,B指向SomeWhereInRing

A向前挪动到M-1位置,即是SomeWhereInRing的前驱节点
B向前挪动N-1节点,则到达SomeWhereInRing前驱节点
退出条件:
假设A和B都在环上,那么A == B。直到A != B,说明A和B都是环起始点的前驱节点
A.next == B.next
此时可以结束,A.next即是环的起始位置

备注:第三步使用递归可降低复杂度



网友最新评论( 3 )

欢迎加入 Typecho 大家族

July 26th, 2018
搜寻

你好 这里安装的时候有个error Notice: Undefined variable: tjids in D:\wamp64\www\typecho\usr\themes\default\functions.php on line 313 怎么搞的

August 13th, 2018
发表我的评论
'
昵称 (必填)
邮箱 (必填)
网址