C语言单链表求环，并返回环的起始节点
若链表中存在环，找出其中的环所在的节点，否则，返回NULL
在没有C++ set容器的优势前提下，我们对这样的环型的寻找以及定位可以利用快慢指针来实现。
有环的存在，类似与操场跑圈，必然存在快慢之分。有了快慢，就一定会有交点。反之，有了交点，就一定存在环。
实现过程如下：
- slow指针移动一次，fast指针移动两次，当fast指针和slow指针相等时保留相等时的节点
- 根据运算，从相等时的节点和头节点以相同的速度运算，当两者相等时即为环的起始节点
算法实现如下：
Data *get_circle_list(Data *head) {Data *fast;Data *slow;fast = head;slow = head;Data *meet = NULL;/*快速和慢速指针一起移动*/while (fast) {fast = fast -> next;slow = slow -> next;if (!fast) {//当快速指针为空时，即不存在环型节点return NULL;}//否则快速指针继续移动fast = fast -> next;if(fast == slow) {meet = fast;break;}}/*如果没有找到相遇的节点，那么即不存在环型*/if(meet == NULL) {return NULL;} else {while (!(head == meet)) {head = head -> next;meet = meet -> next;}return head;}return NULL;
}
源代码测试如下:
#include <stdio.h>
#include <stdlib.h>typedef struct link_list {int data;struct link_list *next;
}Data;void print_list(Data *head) {while (head) {printf("%d ",head->data);head = head -> next;}printf("\n");
}Data *insert_head(Data *head, int n) {head = (Data *)malloc (sizeof(Data));head -> next = NULL;int data;while(n --) {Data *p = (Data *)malloc(sizeof(Data));scanf("%d",&data);p -> data = data;p -> next = head -> next;head -> next = p;}return head;
}Data *insert_tail(Data *head, int n) {head = (Data *)malloc(sizeof(Data));head -> next = NULL;Data *r = head;int data;while(n--) {Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &data);p -> data = data;r -> next = p;r = p;p -> next = NULL;}return head;
}Data *get_circle_list(Data *head) {Data *fast;Data *slow;fast = head;slow = head;Data *meet = NULL;while (fast) {fast = fast -> next;slow = slow -> next;if (!fast) {return NULL;}fast = fast -> next;if(fast == slow) {meet = fast;break;}}if(meet == NULL) {return NULL;} else {while (!(head == meet)) {head = head -> next;meet = meet -> next;}return head;}
}int main() {/*构造环形测试用例*/Data a1,a2,a3,a4,a5,a6,a7;a1.data = 1;a2.data = 2;a3.data = 3;a4.data = 4;a5.data = 5;a6.data = 6;a7.data = 7;a1.next = &a2;a2.next = &a3;a3.next = &a4;a4.next = &a5;a5.next = &a6;a6.next = &a7;/*构造环形，这里很明显环形的起点为5节点*/a7.next = &a5;printf("get circle node \n");Data *result = get_circle_list(&a1);printf("get circle node is %d\n",result -> data);return 0;
}
输出如下:
get circle node
get circle node is 5
相关文章：
CSS3无前缀脚本prefixfree.js与Animatable使用介绍
要求 必备知识 本文要求基本了解 JAVASCRIPT 和 和 CSS3 基本知识。 运行环境 桌面端:IE9 ，Opera 10，火狐3.5 ，Safari 4和Chrome浏览器;移动端:移动Safari，Android浏览器，Chrome浏览器和Opera Mobile。 演示地址 演示…
mysql的优化之table_open_cache 篇_mysql性能优化之table_open_cache
表现：数据库查询效率慢，show processlist 发现比较多的查询正在opening table。进一步确认，执行以下语句：mysql> show global status like open%tables%;------------------------| Variable_name | Value |----------------…
AIX系统日志学习笔记之一
AIX系统上线之后，难免会出现错误，为了应对错误，aix提供了很多处理错误的方法和日志记录机制，为修复故障和系统提供方便。 Errdemon是aix的一个守护进程，该进程会实时检查/dev/drror设备文件，查看是否有新的…
C语言的单链表分割
已知链表头指针head与数值x，将所有小于x的节点放在大于或等于x 的节点前，且保持这些节点的原来的相对位置。 这个过程有点类似于快速排序，寻找一个阈值，比该阈值小的放左边，比该阈值大的放右边。只是由数组遍历变为来…
java面试时候算法题多吗_java程序员面试中最容易被问到的18个算法题（附答案！）...
作者：cpp软件架构狮链接：https://www.toutiao.com/i6618515311836529156/(点击阅读原文前去围观)算法是比较复杂又基础的学科，每个学编程的人都会学习大量的算法。而根据统计，以下这18个问题是面试中最容易遇到的，本文…
Ubantu Mark
说明：由于图形化界面方法（如Add/Remove... 和Synaptic Package Manageer）比较简单，所以这里主要总结在终端通过命令行方式进行的软件包安装、卸载和删除的方法。 一、Ubuntu中软件安装方法 1、APT方式 （1）普…
Linux挂载Windows共享目录
手工挂载： mount -t cifs -o usernameXXX,passwordXXX //IP/共享目录 /挂载目录 自动挂载： 在etc/fstab加入 //IP/共享目录 /挂载目录 cifs defaults,auto,usernameXXX,passwordXXX 0 0 重启转载于:https://blog.51cto.com/kenzhuang/1149033
搭建私有npm私库（使用verdaccio）
一、为什么要搭建npm私库 原因:1）公司内部开发的私有包，统一管理，方便开发和使用；2）安全性，由于公司内部开发的模块和一些内容并不希望其他无关人员能够看到，但是又希望内部能方便使用ÿ…
C语言的有序单链表合并
已知两个已排序链表头节点指针headA与headB，将这两个链表合并，合并后仍为 有序的，返回合并后的头节点。 主要步骤如下： 创建一个临时的头节点，头节点每次指向headA 或者 headB较小的节点当headA->data 比headB-&g…
我的世界java版双海底神殿种子_我的世界海底神殿种子2021
游戏我的世界中，2021年的海底神殿地图中有五种类型的种子可以使用，建议在找海底神殿时使用夜视药水。那么2021年在MC中最新的海底神殿种子分别是Seed：-1005362104，Seed：-1436927780，Seed：-10053…
Erlang服务端开发（无需Erlang基础）笔试题
某游戏公司Erlang服务端开发（无需Erlang基础）笔试题，面向C/C程序员 一、用你熟悉的语言解决下面的问题。 1、反转输出字符串，并移除其中的空格。 2、快速的判断一个数是否素数的方法。 3、给一个数组进行排序。 4、设计一个背包系…
几何匹配和分合算法的图像识别技术
第一章 引言 1.1 面像定位概述及其与面像识别的关系 这个设计所涉及到的是面像的定位和识别。简单来说，所谓面像的定位，就是在照片(静态图像)或视频(动态图像)中标出面像所在的位置，把面像选取出来。而面像的识别就是把选取出来的面像与…
RegExp 正则
正则：就是一条规则，用于检验字符串的格式，目标就是字符串。 只要是表单提交的数据都是字符串 正则的定义： 1.var regnew RegExp()； 2.var reg/格式/； 正则的方法： 两个功能，一个是匹…
C++的多个有序链表合并
已知k个已排序链表头节点指针，将这k个链表合并，合并后仍为有序的 ，返回合并后的头节点 如下三个链表： 合并后的结果如下： 方法一（STL sort算法进行排序）： 先将输入的排序链表插入…
c# 垃圾回收是引用类型而言的
c# 垃圾回收是引用类型而言的转载于:https://www.cnblogs.com/C-CHERS/p/3646387.html
java unlimited_具有无限参数的Java方法(Java method with unlimited arguments)
具有无限参数的Java方法(Java method with unlimited arguments)Spring框架使用方法，您可以根据需要传递尽可能多的参数。我想写一个函数，也可以采取无限量的数据。 这个功能是如何调用的，以便我可以阅读它。 或者我该如何定义它？…
2013-3-10日记
2019独角兽企业重金招聘Python工程师标准>>> 今天星期日，在家早上看NBA，中午去买菜，下午在家种花，晚上看CBA。 转载于:https://my.oschina.net/guanyun/blog/112801
P1522 牛的旅行
这题挺好……有几个坑……（反正我都跳进去了） 对于新的更大的图，由于求的是最小连接边，所以它的值可能小于之前单独一个图的最长的最短路…… 所以之后的值应该取个max（emmm……） 所以第一次我只拿了70。。…
C++ algorithm的sort函数总结
sort函数 sort对给定区间进行排序，支持各种数据类型，迭代器，结构体，自定义排序规则stable_sort 对给定区间进行稳定排序,且可保证相等元素的原本相对次序在排序后保持不变partial_sort 对给定区间部分元素排序partial_sort_copy …
加密解密php,PHP实现的加密解密处理类
本文实例讲述了PHP实现的加密解密处理类。分享给大家供大家参考，具体如下：/* 版权协议： GPL (The GNU GENERAL PUBLIC LICENSE Version 2, June 1991)------------------------------------------------------------ 文件名称：cls…
技术人生：本周改进计划
分配时间学习领域知识和管理知识。更慎重的命名。注意交流的态度和方式（特别是在出现不同意见的时候）。对待任何工作内容都不能应付了事。转载于:https://www.cnblogs.com/happyframework/p/3695596.html
linux下batik-rasterizer.jar生成图片中文乱码
为什么80%的码农都做不了架构师？>>> 发现原来jdk5.0在linux下和以前的版本还不一样，默认不支持中文字体的。得手动去搞一个fontconfig配置， 此文件在$JAVA_HOME/jre/lib/下， 果然有一大堆fontconfig.XX.properties, 官…
小记，springboot项目中自己常用的logback配置文件
把配置文件放到resources这个classpath目录即可生效，日志输入样式是从springboot中日志配置中copy过来的, 其他常用配置不做过多注释了。 logback-spring.xml <?xml version"1.0" encoding"UTF-8"?> <configuration><conversi…
s-sar命令（System Activity Reporter系统活动情况报告）
文章目录前言语法格式查看CPU使用情况保存统计结果到文件中查看磁盘平均负载和队列长度查看内存使用情况查看系统swap分区情况查看IO和传递速率查看磁盘使用情况输出inode、文件和其他内核表的信息统计网络信息查看网络接口信息网络设备通信失败信息统计socket连接信息TCP连接的…
基础设计模式：单例模式+工厂模式+注册树模式
单例模式： 通过提供自身共享实例的访问，单例设计模式用于限制特定对象只能被创建一次。 使用场景： 一般数据库实例都会用单例模式 实现： 单例设计模式就是要一个类只能实例化一个对象。 要想让一个类只能实例化一个对象࿰…
mac 配置 php,mac如何配置php环境
一、启动Apache两种方法1、打开网络共享打开"系统偏好设置"->"共享"，在"互联网共享"那一项前面打√。2、打开终端，输入sudo apachectl start这时需要输入密码，输入电脑密码即可,然后输入sudo apachectl &am…
LinkedBlockingQueue应用实例
并发库中的BlockingQueue是一个比较好玩的类，顾名思义，就是阻塞队列。该类主要提供了两个方法put()和take()，前者将一个对象放到队列中，如果队列已经满了，就等待直到有空闲节点；后者从head取一个对象&#…
s-stat 查看文件或者文件系统的状态信息
命令用法 stat [OPTION]... FILE... -L 查看链接文件-f 查看文件系统信息，而非文件信息-c --format%a 支持使用格式化字符串输出结果，支持\n,\t等转义字符,详细格式化情况使用man stat查看--printfFORMAT 支持格式化输出-t 以简洁的方式输出结果 常用…
梦想的地方！地球上最值得去的20个地方【组图】
如果你是一个热爱大自然的人你肯定会喜欢这个集合。地球上有太多的地方和风景值得我们这辈子至少要去看一次。大多数自然摄影师喜欢没有人出现在他们的照片中，他们想获得纯净、完美的风景，没有人类的影响。这篇文章展示了20个地球上最惊人的地方的照片&a…
php读取js验证码,PHP + JS 实现验证码功能
验证码是网站防止恶意攻击最常用的手段，怎样使用PHP来生成验证码呢，下面就直接上例子首先给出生成验证码的PHP代码：将上面的代码放在一个单独的php文件中，如：auth_code.php，最好不要讲验证码的代码放到其他…