`

单向链表上是否有环

阅读更多

有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。

问题:

1、如何判断一个链表是不是这类链表?
2、如果链表为存在环,如果找到环的入口点?

解答:

1、最简单的方法, 用一个指针遍历链表, 每遇到一个节点就把他的内存地址(java中可以用object.hashcode())做为key放在一个hashtable中. 这样当hashtable中出现重复key的时候说明此链表上有环. 这个方法的时间复杂度为O(n), 空间同样为O(n).

2、使用反转指针的方法, 每过一个节点就把该节点的指针反向:

  1. Boolean reverse(Node *head) {
  2. Node *curr = head;
  3. Node *next = head->next;
  4. curr->next = NULL;
  5. while(next!=NULL) {
  6. if(next == head) {
  7. next->next = curr;
  8. return TRUE;
  9. }
  10. Node *temp = curr;
  11. curr = next;
  12. next = next->next;
  13. curr->next = temp;
  14. }
  15. next = curr->next;
  16. curr ->next = NULL;
  17. while(next!=NULL) {
  18. Node *temp = curr;
  19. curr = next;
  20. next = next->next;
  21. curr->next = temp;
  22. }
  23. return FALSE;
  24. }

 

看上去这是一种奇怪的方法: 当有环的时候反转next指针会最终走到链表头部; 当没有环的时候反转next指针会破坏链表结构(使链表反向), 所以需要最后把链表再反向一次. 这种方法的空间复杂度是O(1), 实事上我们使用了3个额外指针;而时间复杂度是O(n), 我们最多2次遍历整个链表(当链表中没有环的时候).

这个方法的最大缺点是在多线程情况下不安全, 当多个线程都在读这个链表的时候, 检查环的线程会改变链表的状态, 虽然最后我们恢复了链表本身的结构, 但是不能保证其他线程能得到正确的结果.

3、 这是一般面试官所预期的答案: 快指针和慢指针

设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表)

  1. int is_link_list_cicled(Node* head)
  2. {
  3. Node *p = head, *q = head;
  4. while(p && q)
  5. {
  6. if(p == q)
  7. return 1;
  8. p = p-> next;
  9. q = q-> next;
  10. if(!q)
  11. return 0;
  12. q = q-> next;
  13. }
  14. return 0;
  15. }

 

证明步长法的正确性(追击问题,如果有环则肯定可以相遇):

如果链表有环,不妨假设其环长度为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)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下:

  1. slist* FindLoopPort(slist *head)
  2. {
  3. slist *slow = head, *fast = head;
  4. while ( fast && fast->next )
  5. {
  6. slow = slow->next;
  7. fast = fast->next->next;
  8. if ( slow == fast ) break;
  9. }
  10. if (fast == NULL || fast->next == NULL)
  11. return NULL;
  12. slow = head;
  13. while (slow != fast)
  14. {
  15. slow = slow->next;
  16. fast = fast->next;
  17. }
  18. return slow;
  19. }

 

扩展问题:

判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。

比较好的方法有两个:

一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。

二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。

这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点

分享到:
评论

相关推荐

    单向循环链表实现约瑟夫环.zip

    在提供的"单向循环链表实现约瑟夫环.txt"文件中,可能包含了具体的代码实现或者详细解释,包括节点定义、链表操作(如插入、删除)以及约瑟夫环算法的完整流程。通过阅读和理解这个文件,你可以深入学习如何将理论...

    单向链表结点的逐个删除-C语言教程

    单向链表作为一种基础的数据结构,其插入、删除、创建和遍历操作是每个程序员必须熟练掌握的技能。本文将详细介绍如何使用C语言实现单向链表结点的逐个删除。 首先,我们要了解单向链表的基本概念。单向链表是由一...

    用单向循环链表模拟约瑟夫环

    用C语言编写的约瑟夫环问题解决程序,利用单向循环链表存储结构模拟此过程

    C/C++经典约瑟夫环问题——带头结点的单向循环链表

    与普通的单向链表不同,它在第一个元素(头结点)之前额外添加了一个结点,通常这个结点不存储实际数据,而是用作链表的标记。这样做的好处是可以简化对链表的处理,比如在插入和删除操作时,不必区分头结点和普通...

    数据结构单向链表和双向链表

    单向链表上的约瑟夫环问题涉及将人围成一圈,按顺序报数,报到特定数字的人出圈,直到只剩一人。链表可以模拟这个过程,通过调整节点间的链接来实现。 接下来,我们转向双向链表。双向链表与单向链表的主要区别在于...

    单向链表的功能

    单向链表的功能远不止这些,还包括合并两个已排序的链表、判断链表是否有环、获取链表中间节点等。理解和熟练掌握单向链表的操作对于编程学习至关重要,特别是在处理动态数据结构和优化算法效率时。通过实践和练习,...

    lianbiao.rar_单向链表

    单向链表是一种基本的数据结构,它在计算机科学和编程中有着广泛的应用。与数组不同,链表中的元素不是在内存中连续存储的,而是通过指针连接起来,每个节点包含数据部分和指向下一个节点的指针部分。这种存储方式...

    VC++采用单向循环链表实现约瑟夫环

    现在我们有了一个表示约瑟夫环的链表,接下来要实现报数和剔除节点的过程。可以创建一个函数,接受链表头、报数起始值和报数间隔作为参数。该函数将遍历链表,每报数到指定间隔就删除当前节点,然后继续从下一个节点...

    单向链表,双向链表示例

    单向链表和双向链表各有优劣,根据具体需求选择合适的类型。通过理解和掌握链表的原理及C语言实现,可以提高解决问题的能力,为后续学习更高级的数据结构和算法打下坚实基础。提供的压缩包文件提供了实践链表操作的...

    java编写的循环链表来实现约瑟夫环

    循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释

    数据结构:单向循环链表源码

    3. **插入和删除操作**:插入和删除节点的操作与普通单向链表类似,但需要考虑链表是否为空及插入位置的判断。 **单向循环链表常见操作** 1. **创建链表**:初始化链表,通常创建一个节点作为链表的首节点。 2. **...

    C语言实现单向链表的创建、插入,删除节点,和2个链表合并

    总结,本篇文章介绍了C语言实现单向链表的基本操作,包括创建链表、插入节点、删除节点、判断链表是否有环以及合并两个已排序的链表。通过理解这些基本操作,可以为更复杂的数据结构和算法打下坚实的基础。在VC6.0...

    利用单向循环链表存储结构模拟约瑟夫环

    约瑟夫环问题: 编号为1,2,3 n的n个人按顺时针方向围坐一圈,没人持有一个密码。一开始任选一个正整数作为报数上限值m,从第一人开始按顺时针方向报数,报到m停止。报m的人出列,将他的密码作为新的m的值,从他的...

    约瑟夫环单循环链表C语言实现

    题目要求使用C语言编程实现约瑟夫环问题,并通过单向循环链表来管理参与游戏的人。以下是具体的知识点解析: #### 知识点解析 ##### 1. 单向循环链表 单向循环链表是一种特殊的线性表存储结构,其中每个节点包含...

    两列单向链表相同值查询设计

    这里需要注意的是,通常单向链表只需要`next`指针,而此结构体还包含了一个`pre`指针,这实际上是双向链表的结构。为了保持题目要求,我们可以忽略`pre`指针的使用。 2. **初始化链表**:通过`head`和`tail`两个...

    单向循环链表.zip

    单向循环链表是一种常见的数据结构,它在计算机科学中有着广泛的应用,特别是在实现动态数据集合,如列表或队列时。在这个压缩包文件“单向循环链表.zip”中,包含了两个源代码文件——LoopSingle.java和List.java,...

    python判断单向链表是否包括环,若包含则计算环入口的节点实例分析

    本篇文章将深入探讨如何判断单向链表是否包含环,并在存在环的情况下计算环的入口节点。 判断链表中是否存在环的典型方法是使用快慢指针。快慢指针的初始位置都是链表的头节点。快指针每次移动两个节点,而慢指针...

    算法:给定一个链表,判断链表中是否存在环

    链表根据节点间连接关系的不同,可以分为单向链表、双向链表和循环链表。 1. **单向链表**:每个节点只包含一个指向其后继节点的指针。 2. **双向链表**:每个节点包含两个指针,一个指向前驱节点,另一个指向后继...

Global site tag (gtag.js) - Google Analytics