python判断链表是否有环的实例代码

先看下实例代码：

class Node:
  def __init__(self,value=None):
    self.value = value
    self.next = None

class LinkList:
  def __init__(self,head = None):
    self.head = head

  def get_head_node(self):
    """
    获取头部节点
    """
    return self.head

  def append(self,value) :
    """
    从尾部添加元素
    """
    node = Node(value = value)
    cursor = self.head
    if self.head is None:
      self.head = node
    else:
      while cursor.next is not None:
        cursor = cursor.next

      cursor.next = node
      if value==4:
        node.next = self.head

  def traverse_list(self):
    head = self.get_head_node()
    cursor = head
    while cursor is not None:
      print(cursor.value)
      cursor = cursor.next
    print("traverse_over") 

  def hasCycle(self, head):
    """
    :type head: ListNode
    :rtype: bool
    """
    slow=fast=head
    while slow and fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if slow is fast:
        return True
    return False

def main():
  l = LinkList()
  l.append(1)
  l.append(2)
  l.append(3)
  l.append(4)
  head = l.get_head_node()
  print(l.hasCycle(head))
  #l.traverse_list()

if __name__ == "__main__":
  main()

知识点思考：

判断一个单链表是否有环,

可以用 set 存放每一个 节点, 这样每次 访问后把节点丢到这个集合里面.

其实 可以遍历这个单链表, 访问过后,

如果这个节点 不在 set 里面, 把这个节点放入到 set 集合里面.

如果这个节点在 set 里面 , 说明曾经访问过, 所以这个链表有重新 走到了这个节点, 因此一定有环

如果链表都走完了, 把所有的节点都放完了. 还是没有重复的节点, 那说明没有环.

以上就是本次介绍的全部相关知识点内容，感谢大家的学习和对我们的支持。

赞 (0)

相关推荐

  • python环形单链表的约瑟夫问题详解

    题目: 一个环形单链表,从头结点开始向后,指针每移动一个结点,就计数加1,当数到第m个节点时,就把该结点删除,然后继续从下一个节点开始从1计数,循环往复,直到环形单链表中只剩下了一个结点,返回该结点. 这个问题就是著名的约瑟夫问题. 代码: 首先给出环形单链表的数据结构: class Node(object): def __init__(self, value, next=0): self.value = value self.next = next # 指针 class RingLinkedL

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

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

    本文实例讲述了python判断单向链表是否包括环,若包含则计算环入口的节点.分享给大家供大家参考,具体如下: 关于数据结构相关的面试题,经常会问到链表中是否存在环结构的判断,下图就是存在环结构的链表. 那么如何判断链表中是否存在环呢,下面解法的思路是采用快慢指针: 两个指向头节点的指针,fast和slow,一起从头结点开始往后遍历,fast每次移动两个节点,slow每次移动一个节点, 这样,如果存在环结构,那么fast指针在不断绕环过程中,肯定会追上slow指针. # -*- coding:ut

  • Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

    本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表

  • python单向循环链表原理与实现方法示例

    python单向循环链表原理与实现方法示例

    本文实例讲述了python单向循环链表原理与实现方法.分享给大家供大家参考,具体如下: 单向循环链表 单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点. 操作 is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) 在头部添加一个节点 append(item) 在尾部添加一个节点 insert(pos, item) 在指定位置pos添加节点 remove(item) 删除一个节点 se

  • Python3实现的判断环形链表算法示例

    本文实例讲述了Python3实现的判断环形链表算法.分享给大家供大家参考,具体如下: 给定一个链表,判断链表中是否有环. 方案一:快慢指针遍历,若出现相等的情况,说明有环 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self,

  • Python双向循环链表实现方法分析

    本文实例讲述了Python双向循环链表实现方法.分享给大家供大家参考,具体如下: 最近身边的朋友在研究用python来实现数据结构.遇到一个问题就是双向循环链表的实现,改指向的时候总是发蒙. 我自己尝实现了一个python的双向循环链表.附上代码,希望对大家有帮助. 如果不懂什么是双向循环链表的伙伴,需要补习一下数据结构的基础之后哦~~~ 在python当中 用一个类Node 来实现链表的节点,节点数据有三个变量: prev:前驱指针: 用于指向当前节点前一个节点 next: 后继指针  用于指

  • Python实现的单向循环链表功能示例

    本文实例讲述了Python实现的单向循环链表功能.分享给大家供大家参考,具体如下: 概述: 单向循环链表是指在单链表的基础上,表的最后一个元素指向链表头结点,不再是为空. 由图可知,单向循环链表的判断条件不再是表为空了,而变成了是否到表头. 操作 is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) 在头部添加一个节点 append(item) 在尾部添加一个节点 insert(pos, item) 在指定位置pos添加节点 rem

  • python判断链表是否有环的实例代码

    先看下实例代码: class Node: def __init__(self,value=None): self.value = value self.next = None class LinkList: def __init__(self,head = None): self.head = head def get_head_node(self): """ 获取头部节点 """ return self.head def append(self

  • Python 判断 有向图 是否有环的实例讲解

    实例如下: import numpy from numpy import * def dfs( v ): vis[v] = -1 flag = 0 for i in range(n): # print (a[v][i],'---', vis[i] ) if a[v][i] != 0 and vis[i] != -1: dfs(i) vis[i] = 1 else: pass if a[v][i] != 0 and vis[i] == -1: print ('Yes, there is A loo

  • 剑指offer之判断链表是否包含环

    1 问题 判断链表是否包含环 2 思路 2个指针,一个指针走一步,一个指针走2步,如果相遇则有,反之无. 3 代码实现 #include <stdio.h> #include <stdlib.h> #define true 1 #define false 0; typedef struct node { int value; struct node *next; }Node; /* *判断链表是否有环 */ int isCircleList(Node *head) { if (he

  • Python判断中文字符串是否相等的实例

    Python判断两个相等的中文字符串为false,将两个待比较的字符串都把unicode编码设为'utf-8'也不能解决问题,具体原因如下: 1.首先查看待比较两个字符串的编码格式 ,使用命令 import chardet ...... string_code = chardet.detect(string_word) 比较两个字符串的编码结果,如下图所示 一个编码格式为'UTF-8-SIG',另一个编码格式为'utf-8',两个字符串的编码格式不同,所以比较的结果为不相等 出现编码为'UTF-

  • 对python判断是否回文数的实例详解

    设n是一任意自然数.若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数.例如,若n=1234321,则称n为一回文数:但若n=1234567,则n不是回文数. 上面的解释就是说回文数和逆序后的结果是相等的.这就是判断一个数值是否是回文数的标准. 代码也是根据这个思路来实现的. # -*- coding: utf-8 -*- """ Created on Sun Aug 5 09:01:38 2018 @author: FanXiaoLei ""

  • 对python判断ip是否可达的实例详解

    python中使用subprocess来使用shell 关于threading的用法 from __future__ import print_function import subprocess import threading def is_reachable(ip): if subprocess.call(["ping", "-c", "2", ip])==0:#只发送两个ECHO_REQUEST包 print("{0} is a

  • python爬虫判断招聘信息是否存在的实例代码

    在找工作的时候,我们会选择上网查询招聘的信息,或者是通过一些招聘会进行现场面试.但由于信息更新不及时,有一些岗位会出现下架的情况,如果我们不注意的话,可能就扑了空.在时间上耽误了不说,面试的信息也会受到一点点打击.今天小编就教大家python爬虫来判断招聘信息是否存在. 首先这里需要一个判断某条招聘是否还挂在网站上的方法,这个暂时想到了还没弄,然后对于发布时间在两个月之前的数据,就不进行统计计算. 以下是完成代码: { "_id" : ObjectId("5a30ad2068

  • python判断集合的超集方法及实例

    1.说明 可以使用 >= 运算符判断当前集合是否为另一个集合的超集,即判断集合 b 中的所有元素是否都包含在集合 a 中. 2.语法 set_a >= set_b # 相当于set_a.issuperset(set_b) 3.参数 set_a:集合 a. set_b:集合 b. 4.返回值 返回布尔值,如果集合 b 中的所有元素都包含在集合 a 中,则返回 True,否则返回 False. 5.实例 # 创建集合 a = {'赵', '钱', '孙', '李'} b = {'赵', '孙',

  • Python找出最小的K个数实例代码

    题目描述 输入n个整数,找出其中最小的K个数.例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,. 这个题目完成的思路有很多,很多排序算法都可以完成既定操作,关键是复杂度性的考虑.以下几种思路当是笔者抛砖引玉,如果读者有兴趣可以自己再使用其他方法一一尝试. 思路1:利用冒泡法 临近的数字两两进行比较,按照从小到大的顺序进行交换,如果前面的值比后面的大,则交换顺序.这样一趟过去后,最小的数字被交换到了第一位:然后是次小的交换到了第二位,...,依次直到第k个数,停

  • python 批量解压压缩文件的实例代码

    下面给大家介绍python 批量解压压缩文件的实例代码,代码如下所述: #/usr/bin/python#coding=utf-8import os,sys import zipfile open_path='e:\\data'save_path='e:\\data' os.chdir(open_path) #转到路径 #首先,通过zipfile模块打开指定位置zip文件 #传入文件名列表,及列表文件所在路径,及存储路径def Decompression(files,file_path,save

随机推荐