python算法-013判断一个较大的链表是否有环

天上不会掉馅饼，努力奋斗才能梦想成真。

---

先来讲讲废话，最近想法很多。
今年9月份就要开始找工作了，现在的我还远远达不到我想去的岗位的要求。很多方面都差很多，昨天看文章学到个公式还挺有意思的:

offer = 心态 * (实力 + 面试技巧) + 缘分运气

我觉得这公式挺对的，这公式里有心态、实力、面试技巧和缘分运气一共四项因素，只有前三项是我们能控制的。就我自身而言：

• 心态，容易紧张，但是还是比较稳的，不轻易放弃，乐观向上，当然这些还不够，我正在慢慢改进。
• 实力，我觉得这是我最欠缺的。在读大学不是985、211，也不是双一流，当然也有强项，但不是我所在的专业。这些天然的优势我没有，只有靠实力了，这也是最需要花时间的。
• 面试技巧，还没有过正式的面试经验，需要练习。
• 运气。。。。。。。

我现在需要做的是：尽全力提升自身硬实力，拓宽知识面，巩固基础，深挖我感兴趣、有基础的技术。改善心态、提高交流能力。
算算时间，还有大概半年，我能将自己提升到什么地步呢？大家一起见证！
还有一件事，每天的文章是不会断的，这也是提高自己的一个方式。不是为了别的，只为了巩固下自己所学，当然若能帮到大家，我自然更高兴。虽然每天看的人越来越少，但是我会坚持下去的，毕竟有件能坚持的事情是很幸福的。不过，我会尽量减少写文章的时间，增加文章的深度，将进度提到我目前在学的地方。如果大家看过我的GitHub，就会发现，上面的代码有51个了，但是简书才写了十几个，所以我会将简单的放在一起写。今天话有点多了，进入正题吧：

---

题目：给一个长度较大的链表，判断其是否有环存在。例如：

H->1->3->4->6->7->0->2->4
1-          ^           |
            |           7
2-          |           |
            |           v
3-          7<-0<-2<-4<-3

---

这样的链表，尾部的圈便是环，根据单链表的节点定义可知，每个节点只指向其后继节点，所以环一定在链表的尾部。比如图中节点6，它的后继节点是7，就不能再指向其他新的节点了。
我们先来看一下如何获得一个带环的链表呢？前面构造链表的方法我们已经用了12 次了，这里就不多说了。经过上面的分析，可以得知，只需要将没有环的单链表的尾结点指向其前面已经存在的节点就可以形成环。
代码实现：

import random
def constructLinkwithAnnulation(x):
    i = 1
    head = LNode(None)
    tmp = None
    cur = head
    while i <= x:
        n = random.randint(1, 9)
        tmp = LNode(n)
        cur.next = tmp
        cur = tmp
        i += 1
    # 上面的部分 就是之前我们用的构造链表的方法
    #这里我是设置了二分之一的概率产生有环的链表
    if random.randint(0,1)==1:
        m = random.randint(1, x - 1)  # 用于选择出环的入口是哪个
        Annulation=head.next # 用于遍历到选定的节点，就是出环的入口
        while m>0:
            Annulation=Annulation.next
            m-=1
        # 因为前面构造链表时就用了cur，最后他指向了最后一个节点
        cur.next=Annulation #这里将尾结点的next域指向环入口
    return head

打印出来如下图，因为环的原因，会一直循环打印，我截取一段。链表长度为10：

环

好的环有了，接下来就是如何不看链表判断他是否有环了。这边节省时间我就直接讲了，有两个方法一个是蛮力HashSet法，一个是指针法。

先来介绍蛮力法：遍历整个链表，将遍历到的节点的next域的值存到集合中，这里保存next域，不保存data域是因为，因为链表比较长，data可能会相同。当然也可以直接保存整个节点。然后再遍历时判断当前节点的next域是否在集合中，如果有相同的则存在环，否则无环。
代码实现：

def HaveAnnulation(head):
    #判断链表是否为空
    if head.next is None or head.next is None:
        return None
    #建立一个集合
    HashSet=set()
    #格式化集合
    HashSet.clear()
    #开始遍历链表
    tmp=head.next
    while tmp.next is not None:
        #判断当前节点的next域是否在集合中
        if tmp.next not in HashSet:
            #如果不在，就加入集合中
            HashSet.add(tmp.next)
            tmp=tmp.next
        else:
            #如果在返回True
            return True
    return False

这种办法好与坏一会介绍，先来说快慢指针法：昨天说了先后指针法，其实差不多，用两个指针fast和slow，先指向链表头，然后同时开始遍历，slow每次一步，fast每次两步，即slow=slow.next``fast=fast.next.next。除了第一次，每次遍历都要比较 slow和fast是否相等，如果相等，则有环。如果fast遍历完了也没有相等，则无环。
代码实现：

def HaveAnnulation(head):
    #判断链表是否为空
    if head.next is None or head.next is None:
        return None
    #都指向第一个节点
    slow=head.next
    fast=head.next
    #开始遍历
    while fast is not None:
        #这里注意一定先操作再判断，因为如果先判断的话，
        # 第一个节点就是相等的
        slow = slow.next
        fast = fast.next.next
        if slow==fast:
            #这里直接判断两个节点是否完全相等
            return True
    return False

我先给出蛮力法的全部代码：

import random
import time
class LNode:
    def __init__(self,arg):
        self.data=arg
        self.next=None

"""
题目描述：
链表中的某个节点的next域指向的是链表中在他之前的某一个节点，这样在链表尾部形成了环的结构。如何判断链表中是否有环的结构
要求：
方法：HashSet蛮力法
"""
def creatLinkwithAnnulation(x):
    i = 1
    head = LNode(None)
    tmp = None
    cur = head
    while i <= x:
        n = random.randint(1, 9)
        tmp = LNode(n)
        cur.next = tmp
        cur = tmp
        i += 1
    # 上面的部分 就是之前我们用的构造链表的方法
    #这里我是设置了二分之一的概率产生有环的链表
    if random.randint(0,2)==0:
        m = random.randint(1, x - 1)  # 用于选择出环的入口是哪个
        Annulation=head.next # 用于遍历到选定的节点，就是出环的入口
        while m>0:
            Annulation=Annulation.next
            m-=1
        # 因为前面构造链表时就用了cur，最后他指向了最后一个节点
        cur.next=Annulation #这里将尾结点的next域指向环入口
    return head
def judgeAnnulation(head):
    #判断链表是否为空
    if head.next is None or head.next is None:
        return None
    #建立一个集合
    HashSet=set()
    #格式化集合
    HashSet.clear()
    #开始遍历链表
    tmp=head.next
    while tmp.next is not None:
        #判断当前节点的next域是否在集合中
        if tmp.next not in HashSet:
            #如果不在，就加入集合中
            HashSet.add(tmp.next)
            tmp=tmp.next
        else:
            #如果不在返回False
            return True
    return False
if __name__ == '__main__':
    start = time.time()
    head = creatLinkwithAnnulation(10000)
    end = time.time()
    print("创建用时：", end - start)

    cur = head.next
    start=time.time()
    buer=judgeAnnulation(head)
    end=time.time()
    print("判断用时：",end-start)
    if buer == False:
        print("head中无环")
    elif buer == True:
        print("head中有环")
    else:
        print("head为空")

结果：

image.png
image.png

然后是快慢指针法：

import random
import time
class LNode:
    def __init__(self,arg):
        self.data=arg
        self.next=None

"""
题目描述：
链表中的某个节点的next域指向的是链表中在他之前的某一个节点，这样在链表尾部形成了环的结构。如何判断链表中是否有环的结构
要求：
方法：HashSet蛮力法
"""
def constructLinkwithAnnulation(x):
    i = 1
    head = LNode(None)
    tmp = None
    cur = head
    while i <= x:
        n = random.randint(1, 9)
        tmp = LNode(n)
        cur.next = tmp
        cur = tmp
        i += 1
    # 上面的部分 就是之前我们用的构造链表的方法
    #这里我是设置了二分之一的概率产生有环的链表
    if random.randint(0,1)==0:
        m = random.randint(1, x - 1)  # 用于选择出环的入口是哪个
        Annulation=head.next # 用于遍历到选定的节点，就是出环的入口
        while m>0:
            Annulation=Annulation.next
            m-=1
        # 因为前面构造链表时就用了cur，最后他指向了最后一个节点
        cur.next=Annulation #这里将尾结点的next域指向环入口
    return head
def judgeAnnulation(head):
    #判断链表是否为空
    if head.next is None or head.next is None:
        return None
    #都指向第一个节点
    slow=head.next
    fast=head.next
    #开始遍历
    while fast is not None:
        #这里注意一定先操作再判断，因为如果先判断的话，
        # 第一个节点就是相等的
        slow = slow.next
        fast = fast.next.next
        if slow==fast:
            #这里直接判断两个节点是否完全相等
            return True
    return False
if __name__ == '__main__':
    start = time.time()
    head = constructLinkwithAnnulation(100)
    end = time.time()
    print("创建用时：", end - start)
    cur = head.next
    start1=time.time()
    buer=judgeAnnulation(head)
    end1=time.time()
    print("判断用时：",end1-start1)
    if buer == True:
        print("head中有环")
    elif buer == False:
        print("head中没环")
    else:
        print("head为空")

image.png

本来打算写找环出口的，明天吧。没准备好。
晚安。