有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。
问题:
1、如何判断一个链表是不是这类链表?
2、如果链表为存在环,如果找到环的入口点?
解答:
1、最简单的方法, 用一个指针遍历链表, 每遇到一个节点就把他的内存地址(java中可以用object.hashcode())做为key放在一个hashtable中. 这样当hashtable中出现重复key的时候说明此链表上有环. 这个方法的时间复杂度为O(n), 空间同样为O(n).
2、使用反转指针的方法, 每过一个节点就把该节点的指针反向:
- Boolean reverse(Node *head) {
- Node *curr = head;
- Node *next = head->next;
- curr->next = NULL;
- while(next!=NULL) {
- if(next == head) {
- next->next = curr;
- return TRUE;
- }
- Node *temp = curr;
- curr = next;
- next = next->next;
- curr->next = temp;
- }
- next = curr->next;
- curr ->next = NULL;
- while(next!=NULL) {
- Node *temp = curr;
- curr = next;
- next = next->next;
- curr->next = temp;
- }
- return FALSE;
- }
看上去这是一种奇怪的方法: 当有环的时候反转next指针会最终走到链表头部; 当没有环的时候反转next指针会破坏链表结构(使链表反向), 所以需要最后把链表再反向一次. 这种方法的空间复杂度是O(1), 实事上我们使用了3个额外指针;而时间复杂度是O(n), 我们最多2次遍历整个链表(当链表中没有环的时候).
这个方法的最大缺点是在多线程情况下不安全, 当多个线程都在读这个链表的时候, 检查环的线程会改变链表的状态, 虽然最后我们恢复了链表本身的结构, 但是不能保证其他线程能得到正确的结果.
3、 这是一般面试官所预期的答案: 快指针和慢指针
设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表)
- int is_link_list_cicled(Node* head)
- {
- Node *p = head, *q = head;
- while(p && q)
- {
- if(p == q)
- return 1;
- p = p-> next;
- q = q-> next;
- if(!q)
- return 0;
- q = q-> next;
- }
- return 0;
- }
证明步长法的正确性(追击问题,如果有环则肯定可以相遇):
如果链表有环,不妨假设其环长度为M(>=2)。
p指针首次到达交点(N0)时,q指针已经进入环。
设p=0;q=q-p;
再进过i(i>=0)步后,p=(p+i)%m;q=(q+2*i)%m;
则必存在一个i使得(p+i)%m = (q+2*i)%m。(p,q 都为常数)。
二、找到环的入口点
当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)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下:
- 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)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点
相关推荐
在提供的"单向循环链表实现约瑟夫环.txt"文件中,可能包含了具体的代码实现或者详细解释,包括节点定义、链表操作(如插入、删除)以及约瑟夫环算法的完整流程。通过阅读和理解这个文件,你可以深入学习如何将理论...
单向链表作为一种基础的数据结构,其插入、删除、创建和遍历操作是每个程序员必须熟练掌握的技能。本文将详细介绍如何使用C语言实现单向链表结点的逐个删除。 首先,我们要了解单向链表的基本概念。单向链表是由一...
用C语言编写的约瑟夫环问题解决程序,利用单向循环链表存储结构模拟此过程
与普通的单向链表不同,它在第一个元素(头结点)之前额外添加了一个结点,通常这个结点不存储实际数据,而是用作链表的标记。这样做的好处是可以简化对链表的处理,比如在插入和删除操作时,不必区分头结点和普通...
单向链表上的约瑟夫环问题涉及将人围成一圈,按顺序报数,报到特定数字的人出圈,直到只剩一人。链表可以模拟这个过程,通过调整节点间的链接来实现。 接下来,我们转向双向链表。双向链表与单向链表的主要区别在于...
单向链表的功能远不止这些,还包括合并两个已排序的链表、判断链表是否有环、获取链表中间节点等。理解和熟练掌握单向链表的操作对于编程学习至关重要,特别是在处理动态数据结构和优化算法效率时。通过实践和练习,...
单向链表是一种基本的数据结构,它在计算机科学和编程中有着广泛的应用。与数组不同,链表中的元素不是在内存中连续存储的,而是通过指针连接起来,每个节点包含数据部分和指向下一个节点的指针部分。这种存储方式...
现在我们有了一个表示约瑟夫环的链表,接下来要实现报数和剔除节点的过程。可以创建一个函数,接受链表头、报数起始值和报数间隔作为参数。该函数将遍历链表,每报数到指定间隔就删除当前节点,然后继续从下一个节点...
单向链表和双向链表各有优劣,根据具体需求选择合适的类型。通过理解和掌握链表的原理及C语言实现,可以提高解决问题的能力,为后续学习更高级的数据结构和算法打下坚实基础。提供的压缩包文件提供了实践链表操作的...
循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释
3. **插入和删除操作**:插入和删除节点的操作与普通单向链表类似,但需要考虑链表是否为空及插入位置的判断。 **单向循环链表常见操作** 1. **创建链表**:初始化链表,通常创建一个节点作为链表的首节点。 2. **...
总结,本篇文章介绍了C语言实现单向链表的基本操作,包括创建链表、插入节点、删除节点、判断链表是否有环以及合并两个已排序的链表。通过理解这些基本操作,可以为更复杂的数据结构和算法打下坚实的基础。在VC6.0...
约瑟夫环问题: 编号为1,2,3 n的n个人按顺时针方向围坐一圈,没人持有一个密码。一开始任选一个正整数作为报数上限值m,从第一人开始按顺时针方向报数,报到m停止。报m的人出列,将他的密码作为新的m的值,从他的...
题目要求使用C语言编程实现约瑟夫环问题,并通过单向循环链表来管理参与游戏的人。以下是具体的知识点解析: #### 知识点解析 ##### 1. 单向循环链表 单向循环链表是一种特殊的线性表存储结构,其中每个节点包含...
这里需要注意的是,通常单向链表只需要`next`指针,而此结构体还包含了一个`pre`指针,这实际上是双向链表的结构。为了保持题目要求,我们可以忽略`pre`指针的使用。 2. **初始化链表**:通过`head`和`tail`两个...
单向循环链表是一种常见的数据结构,它在计算机科学中有着广泛的应用,特别是在实现动态数据集合,如列表或队列时。在这个压缩包文件“单向循环链表.zip”中,包含了两个源代码文件——LoopSingle.java和List.java,...
本篇文章将深入探讨如何判断单向链表是否包含环,并在存在环的情况下计算环的入口节点。 判断链表中是否存在环的典型方法是使用快慢指针。快慢指针的初始位置都是链表的头节点。快指针每次移动两个节点,而慢指针...
链表根据节点间连接关系的不同,可以分为单向链表、双向链表和循环链表。 1. **单向链表**:每个节点只包含一个指向其后继节点的指针。 2. **双向链表**:每个节点包含两个指针,一个指向前驱节点,另一个指向后继...