问题:
1、如何判断一个链表是不是这类链表?
2、如果链表为存在环,如果找到环的入口点?
解答:
一、判断链表是否存在环,办法为:
设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表)程序如下:
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肯定没有走遍历完链表,见注释(1)而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)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下:
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;
}
分享到:
相关推荐
笔试时,常见的题型。判断单链表中是否存在环
在Java中,判断单链表是否有环的经典方法是使用Floyd的“龟兔赛跑”算法,也称为快慢指针法。这种方法利用两个指针,一个每次走一步(称为慢指针),另一个每次走两步(称为快指针)。如果链表中存在环,那么快指针...
通过Java实现单链表的操作,包括单链表定义、遍历、置空、判空、插入、删除、反转、中间结点、指定顺序排序、前插、后插、判断单链表是否存在环、环的长度、环的起始结点
附件是使用双指针发判断链表有环的代码实现,在Java中,判断单链表是否有环的经典方法是使用Floyd的“龟兔赛跑”算法,也称为快慢指针法。这种方法利用两个指针,一个每次走一步(称为慢指针),另一个每次走两步...
包括如下操作:初始化、销毁、清空、求长度、遍历 指定位置插入和删除元素 按位置和按元素值查找 查找并删除单链表中值域为e的全部结点 ... 建环/判断环存在 删除重复元素 合并两种有序单链表
二叉树的层次遍历及宽度,哈夫曼树,将L中的整数序列循环左移p个位置,将表L中所有值为x 的元素删除,判断链表中是否存在环,删除单链表L(L中元素值各不相同)的最大值所对应的结点,并返回该值,树的孩子兄弟表示...
判断一个单链表中,是否存在环。采用双指针,一快一慢,判断两指针在多次迭代后,是否相遇。即龟兔算法。
3.1 判断字符串是否为回文 3.2 实现strStr() 3.3 字符串转为int(atoi) 3.4 二进制树相加 3.5 最长回文字符串 3.6 正则表达式匹配[hard] 3.7 正则匹配 3.8 最长公共前缀 3.9 验证字符串是否为数字 3.10 数字转为...
双向链表也可以有循环表,链表中存在两个环。一个结点的前趋的后继和该结点的后继的前趋都是指向该结点的。 p == p→lLink→rLink == p→rLink→lLink 2.2 栈 栈(Stack)是限定仅在表尾进行插入或删除操作...
实例104 判断一个数是否存在数组中 135 实例105 求二维数组对角线之和 136 实例106 模拟比赛打分 137 实例107 矩阵的转置 139 实例108 设计魔方阵 141 实例109 字符升序排列 142 实例110 在指定位置插入字符 144 ...
d. 当输入一个商品时,能显示该商品是否在库存中,如存在库存中,则显示其名称和数量,否则显示“未找到”。 e. 如有可能,请建立一个存储商品名称和数量的文本文件,并为二叉搜索树建立一个成员函数...
1.2.8. 判断整数序列是不是二元查找树的后序遍历结果 ................................ 33 1.2.9. 查找最小的 K 个元素-使用最大堆....................................................... 35 1.2.10. 求二叉树中...
例:若程序执行时,输入字符串为:Shanghai Dianji University,从键盘上输入字符:s,则输出后变为:Shanghai Dianji Univerity,如果输入的字符串不存在,则字符串照原样输出。 (9)编写一个函数void fun(char a...