首页 > 代码库 > 010给定一个循环链表，实现一个算法返回这个环的开始结点 （keep it up）
010给定一个循环链表，实现一个算法返回这个环的开始结点 （keep it up）
给定一个循环链表，实现一个算法返回这个环的开始结点。
定义：
循环链表：链表中一个结点的指针指向先前已经出现的结点，导致链表中出现环。
例子：
输入：A -> B -> C -> D -> E -> C [结点C在之前已经出现过]
定义：
循环链表：链表中一个结点的指针指向先前已经出现的结点，导致链表中出现环。
例子：
输入：A -> B -> C -> D -> E -> C [结点C在之前已经出现过]
输出：结点C
可以用一个map<node*,bool> 就解决问题了。
下面是编程之美上一种奇特的解法：快慢指针解法。
代码：
struct SNode
{
int data;
SNode* next;
};
SNode* findCirleStart(const SNode* vHead)
{
if (vHead->next == NULL) return NULL;
SNode* Fast = vHead;
SNode* Slow = vHead;
while (Slow && Fast->next)
{
Slow = Slow->next;
Fast = Fast->next->next;
if (Slow == Fast) break;
}
Slow = vHead;
while (Slow != Fast)
{
Slow = Slow->next;
Fast = Fast->next;
}
return Fast;
}010给定一个循环链表，实现一个算法返回这个环的开始结点 （keep it up）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。