判断单链表是否有环,并找出环的入口【python】



参考链接:数据结构面试 之 单链表是否有环及环入口点 附有最详细明了的图解 – 简书 https://www.jianshu.com/p/ef71e04241e4

判断单向列表是否包括环,若包含,环入口的节点计算 python实现 – 鲸落丶 – 博客园 https://www.cnblogs.com/kunpengv5/p/7784791.html

判断链表是否有环以及环的入口点(转载) – 天马行空 – ITeye博客 http://superwind.iteye.com/blog/706887

问题:

1、如何判断一个链表是否有环?

2、如果链表为存在环,如果找到环的入口点?

 

1.限制与要求

  • 不允许修改链表结构。
  • 时间复杂度O(n),空间复杂度O(1)。

2.思考

2.1判断是否有环

如果链表有环,那么在遍历链表时则会陷入死循环,利用这个特征,我们可以设计这样的算法。

  • 使用一个slow指针,一个fast指针。
  • slow指针一次往后遍历以1个节点,fast指针一次往后遍历2个节点,一直做这样的操作。

《判断单链表是否有环,并找出环的入口【python】》

  • 如果fast指针在遍历过程中,遍历到了NULL节点说明链表没有环。

《判断单链表是否有环,并找出环的入口【python】》

《判断单链表是否有环,并找出环的入口【python】》

《判断单链表是否有环,并找出环的入口【python】》

  • 否则当slow指针和falst指针相同,则说明环有节点。

《判断单链表是否有环,并找出环的入口【python】》

2.2环的入口节点

我们假定链表头到环入口的距离是len,环入口到slow和fast交汇点的距离为x,环的长度为R。slow和fast第一次交汇时,设slow走的长度为:d = len + x,而fast走的长度为:2d = len + nR + x,(n >= 1),从而我们可以得知:2len + 2x = len + nR + x,即len = nR – x,(n >= 1),于是我们可以得到这样的算法。

  • 使用一个cur指针指向链表头节点,一个inter指针指向第一次的交汇点。

《判断单链表是否有环,并找出环的入口【python】》

  • cur指针和inter指针一起往后遍历。

《判断单链表是否有环,并找出环的入口【python】》

《判断单链表是否有环,并找出环的入口【python】》

  • cur指针和inter指针相等时,cur和inter指针指向的就是环的入口节点。

《判断单链表是否有环,并找出环的入口【python】》

 

inter指针在遍历过程中可能多次(n >= 1)经过环入口节点,但当cur指针第一次达到入口节点时,inter指针此时必然也指向入口节点。

 

python 代码:

  class Node(): #定义一个Node类,构造两个属性,一个是item节点值,一个是节点的下一个指向
      def __init__(self,item=None):
          self.item = item
          self.next = None

 def findbeginofloop(head):#判断是否为环结构并且查找环结构的入口节点
     slowPtr = head         #将头节点赋予slowPtr
     fastPtr = head         #将头节点赋予fastPtr
     loopExist =False       #默认环不存在,为False
     if head == None:       #如果头节点就是空的,那肯定就不存在环结构
         return False
     while fastPtr.next != None and fastPtr.next.next != None:      #fastPtr的下一个节点和下下个节点都不为空
         slowPtr = slowPtr.next           #slowPtr每次移动一个节点
         fastPtr = fastPtr.next.next      #fastPtr每次移动两个节点 
         if slowPtr == fastPtr :          #当fastPtr和slowPtr的节点相同时,也就是两个指针相遇了
             loopExist = True
             print("存在环结构")
             break

     if loopExist == True:
         slowPtr  = head
         while slowPtr != fastPtr:
             fastPtr = fastPtr.next
             slowPtr = slowPtr.next
         return slowPtr

     print("不是环结构")
     return False

 if __name__ == "__main__":
     node1 = Node(1)
     node2 = Node(2)
     node3 = Node(3)
     node4 = Node(4)
     node5 = Node(5)
     node1.next = node2
     node2.next = node3
     node3.next = node4
     node4.next = node5
     node5.next = node2
     print(findbeginofloop(node1).item)

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode * detectCycle(ListNode * head) {
        if (NULL == head) return NULL;
        ListNode * fast = head;
        ListNode * slow = head;
        
        while (1)
        {
            fast = fast->next ? fast->next : NULL;
            if (NULL == fast) break;
            
            fast = fast->next ? fast->next : NULL;
            if (NULL == fast) break;
            
            slow = slow->next;
    
            if (slow == fast) break;
        }
        
        if (NULL == fast) return NULL;
        
        ListNode * cur = head;
        ListNode * inter = slow;
        
        while (cur != inter)
        {
            cur = cur->next;
            inter = inter->next;
        }
        
        return cur;
    }
};

扩展问题:

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

比较好的方法有两个:

 

思路1:暴力思路,n方复杂度。对两个链表分别进行遍历,找到相同的节点即可O(n*m),空间复杂度为O(1)。

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

思路3:使用哈希表,即python中的字典。先遍历一个链表,并将链表内容放入字典。再遍历另外一个链表,看遍历到的位置是否存在于字典中,存在则返回当前结点。若遍历结束仍不存在则返回空。检索复杂度为O(m+n),空间复杂度O(m+n)

思路4:先分别计算两个链表的长度。先读较长的链表,读到两个链表等长的时候再同时读两个链表,并判断两个链表遍历到的当前节点是否相同。检索复杂度为O(m+n),空间复杂度为O(1)

参考链接:LeetCode–Intersection of Two Linked Lists (两个链表的交点)Python – 诚实的小小乐 – CSDN博客 https://blog.csdn.net/xiaoxiaoley/article/details/78687405 

 

思路5:将两个链表分别转换为两个列表,从列表的尾部开始对比两个列表的节点是否相等,并进行相应操作,时间复杂度O(n),额外申请空间O(n)

Python实现”相交链表”的三种方法 – qiubingcsdn的博客 – CSDN博客 https://blog.csdn.net/qiubingcsdn/article/details/82619768

 





    原文作者:emmajinxin
    原文地址: https://blog.csdn.net/yangnianjinxin/article/details/79025768
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞