转载:http://www.cppblog.com/humanchao/archive/2008/04/17/47357.html
作者:胡满超 from:C++博客
有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。
问题:
1、如何判断一个链表是不是这类链表?
2、如果链表为存在环,如果找到环的入口点?
一、判断链表是否存在环,办法为:
设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表)程序如下:
Cpp代码
1.bool IsExitsLoop(slist *head)
2.{
3. slist *slow = head, *fast = head;
4.
5. while ( fast && fast->next )
6. {
7. slow = slow->next;
8. fast = fast->next->next;
9. if ( slow == fast ) break;
10. }
11.
12. return !(fast == NULL || fast->next == NULL);
13.}
bool IsExitsLoop(slist *head)
{
slist *slow = head, *fast = head;
while ( fast && fast->next )
{
slow = slow->next;
fast = fast->next->next;
if ( slow == fast ) break;
}
return !(fast == NULL || fast->next == NULL);
}
二、找到环的入口点
当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则 fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:
2s = s + nr
s= nr
设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)
(L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下:
Java代码
1.slist* FindLoopPort(slist *head)
2.{
3. slist *slow = head, *fast = head;
4.
5. while ( fast && fast->next )
6. {
7. slow = slow->next;
8. fast = fast->next->next;
9. if ( slow == fast ) break;
10. }
11.
12. if (fast == NULL || fast->next == NULL)
13. return NULL;
14.
15. slow = head;
16. while (slow != fast)
17. {
18. slow = slow->next;
19. fast = fast->next;
20. }
21.
22. return slow;
23.}
slist* FindLoopPort(slist *head)
{
slist *slow = head, *fast = head;
while ( fast && fast->next )
{
slow = slow->next;
fast = fast->next->next;
if ( slow == fast ) break;
}
if (fast == NULL || fast->next == NULL)
return NULL;
slow = head;
while (slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
扩展问题:
判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。
比较好的方法有两个:
一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。
二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。
这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点。
分享到:
相关推荐
由于要面试所以总结了面试中经常出现的关于单链表方面的问题,希望对大家有所帮助
单链表的基本操作:建立,查找,插入,删除等。 检查单链表是不是有环。 寻找单链表的中间元素。 单链表反转。
算法大全-面试题-链表-栈-二叉树-数据结构.docx 一、单链表 目录 1.单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 ...删除单链表中重复的元素
目录 1.单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个...13.删除单链表中重复的元素
此外,本书开始用两章篇幅详细介绍了中英文面试的注意事项、常见问题及程序员的职业规划等软件工程师的常识。最后四章详细讲解了现在流行的智力测试题。 第一篇 求职 第1章 应聘求职 1.1 企业与人才 1.1.1 企业需要...
题一、给定单链表,检测是否有环。题二、 给定两个单链表(head1, head2),检测两个链表是否有交点,如果有返回第一个交点。等面试题。
那就只能从头遍历一次找到倒数第二个节点了。此外,这道题目的一个变身就是将一个环状单链表拆开(即删除其中一个元素),此时,只要使用上面那两行代码就可以了,不需要考
7. 如何在链表中检测环? 8. 解释堆结构及其在排序中的应用。 9. 如何找出数组中的重复元素? 10. 如何反转单链表? 11. 什么是二叉搜索树? 12. 什么是动态数组,如何实现? 13. 解释图的表示方法:邻接矩阵和邻接...
环形单链表的约瑟夫问题 一个鉴定链表是否为回文结构 将单向链某值分割成小表、送、按右边大的形式 复制带有日常指针的节点表 两个单链表生成相加链表 两个单链表相交的问题 将单链表的每K个节点之间逆序 二叉树问题...
目录 链表(Linked List)介绍【单链表篇】 单链表介绍 单链表模拟 1. 定义pojo 2. 定义内部类SingleLinkedList 管理我们的pojo对象,并实现增删改... 链表是有序的列表,但是它在内存中是存储如下 1)链表是以节
//当单链表中没有环时返回null,有环时返回环的入口结点 public static LNode searchEntranceNode(LNode L) { LNode slow=L;//p表示从头结点开始每次往后走一步的指针 LNode fast=L;//q表示从头结点开始每次往后走两...
PHP高级工程面试题汇总(2018.05) 1、给你四个坐标点,判断它们能不能组成一个矩形,如判断([0,0],[0,1],[1,1],[1,0])能组成一... //当单链表中没有环时返回null,有环时返回环的入口结点 public static LNode searchEn
蓄水池算法 leetcode leetcode ...单链表中的环,两个单链表的公共点。 populating-next-right-pointers-in-each-node-ii: 二级指针代码虽然简洁优雅,但是对性能有影响,不如一级指针加if else判断快。
主要介绍了Java采用循环链表结构求解约瑟夫问题的解决方法,是很多Java面试环节都会遇到的经典考题,这里详细给出了约瑟夫问题的原理及Java解决方法,是非常经典的应用实例,具有一定的参考借鉴价值,需要的朋友可以参考...
//当单链表中没有环时返回null,有环时返回环的入口结点 public static LNode searchEntranceNode(LNode L) { LNode slow=L;//p表示从头结点开始每次往后走一步的指针 LNode fast=L;//q表示从头结点开始每次往后走两...
CD49:在单链表和双链表中删除倒数第K个节点 CD106:删除链表的中间节点和a/b处的节点 CD107:反转单向和双向链表 CD108:反转部分单向链表 CD109:环形单链表的约瑟夫问题(进阶,CD110) CD111:判断一个链表是否...
包括:单向链表的添加、遍历、修改、删除,常见面试题:单向链表有效个数、查找倒数第K个节点、单链表反转、反向遍历链表 主要包含双向链表:com.imyiren.datastructure.linkedlist.DoubleLinkedList 包括:双向链表...
2.9 链表环相关问题 2.9.1 链表是否有环 2.9.2 链表环的入口 2.10 改变链表中的元素位置2.11 LRU Cache(设计题) 3. 字符串 3.1 判断字符串是否为回文 3.2 实现strStr() 3.3 字符串转为int(atoi) 3.4 二进制树...
我做的题目都是经典题目, 基本都包含吧. 可以浏览一下目录, 点进去感兴趣的 , 看看我的个人理解吧. 我觉得我理解的比较简单, 也挺容易懂的. 别把算法定义的太高级的概念吓跑了. 其实学习算法对于编程的提升很大的...
涵盖单链表和双链表。 跳过列表。 跳过列表是一种概率数据结构,具有与 AVL/ 或红黑树相同的对数时间界限和效率,并提供了一种巧妙的折衷,以有效地支持搜索和更新操作。 树木 树。 一个通用的树结构。 二叉树。 每...