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 里面 , 说明曾经访问过, 所以这个链表有重新 走到了这个节点, 因此一定有环
如果链表都走完了, 把所有的节点都放完了. 还是没有重复的节点, 那说明没有环.
以上就是本次介绍的全部相关知识点内容,感谢大家的学习和对我们的支持。
相关推荐
-
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数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表
-
python环形单链表的约瑟夫问题详解
题目: 一个环形单链表,从头结点开始向后,指针每移动一个结点,就计数加1,当数到第m个节点时,就把该结点删除,然后继续从下一个节点开始从1计数,循环往复,直到环形单链表中只剩下了一个结点,返回该结点. 这个问题就是著名的约瑟夫问题. 代码: 首先给出环形单链表的数据结构: class Node(object): def __init__(self, value, next=0): self.value = value self.next = next # 指针 class RingLinkedL
-
python单向循环链表原理与实现方法示例
本文实例讲述了python单向循环链表原理与实现方法.分享给大家供大家参考,具体如下: 单向循环链表 单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点. 操作 is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) 在头部添加一个节点 append(item) 在尾部添加一个节点 insert(pos, item) 在指定位置pos添加节点 remove(item) 删除一个节点 se
-
Python双向循环链表实现方法分析
本文实例讲述了Python双向循环链表实现方法.分享给大家供大家参考,具体如下: 最近身边的朋友在研究用python来实现数据结构.遇到一个问题就是双向循环链表的实现,改指向的时候总是发蒙. 我自己尝实现了一个python的双向循环链表.附上代码,希望对大家有帮助. 如果不懂什么是双向循环链表的伙伴,需要补习一下数据结构的基础之后哦~~~ 在python当中 用一个类Node 来实现链表的节点,节点数据有三个变量: prev:前驱指针: 用于指向当前节点前一个节点 next: 后继指针 用于指
-
python判断单向链表是否包括环,若包含则计算环入口的节点实例分析
本文实例讲述了python判断单向链表是否包括环,若包含则计算环入口的节点.分享给大家供大家参考,具体如下: 关于数据结构相关的面试题,经常会问到链表中是否存在环结构的判断,下图就是存在环结构的链表. 那么如何判断链表中是否存在环呢,下面解法的思路是采用快慢指针: 两个指向头节点的指针,fast和slow,一起从头结点开始往后遍历,fast每次移动两个节点,slow每次移动一个节点, 这样,如果存在环结构,那么fast指针在不断绕环过程中,肯定会追上slow指针. # -*- coding:ut
-
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
随机推荐
- PHP解密Unicode及Escape加密字符串
- MongoDB教程之索引介绍
- IOS实现微信朋友圈相册评论界面的翻转过渡动画
- js倒计时代码
- ASP.NET Razor模板引擎中输出Html的两种方式
- phpStudy 2016 使用教程详解(支持PHP7)
- 基于PHP对XML的操作详解
- PHP用户验证和标签推荐的简单使用
- PHP 和 MySQL 开发的 8 个技巧
- js 将图片连接转换成base64格式的简单实例
- MySQL性能优化的最佳20+条经验
- PHP 字符串操作入门教程
- 慕课网题目之js实现抽奖系统功能
- VBS教程:函数-Second 函数
- Java定时任务的三种实现方法
- 从千千静听歌词服务器获取lrc歌词示例分享
- android在root模式下接听来电的方法
- java多线程解决生产者消费者问题
- 二叉树前序遍历的非递归算法
- java编程约瑟夫问题实例分析