国庆,同学来我这里,疯了几天,什么都没学,好有罪恶感,关键是学习有点进入不了状态,看到两个小算法题,找找学习的感觉
一、检查链表中是否有环
题目描述:
给定一个单链表,判定其中是否有环,即链表的最后一个结点的next指针不是空指针,而是指向了链表中的某一个结点。
思考:
假设最后一个结点的next指针指向的是头结点,即:1->2->3->4->5->1,
整体成环,这种情况比较好解决,只需一个指针指向头结点,另一个指针向后遍历,当两个指针指向同一结点时,可以判定是有环的。
假设最后一个结点的next指针指向的是除头结点外的某一结点,如:1->2->3->4->5->3,
局部成环,这种情况就不能用一个指针指向某一指定的结点,然后遍历,从而判断是否为环,因为这一“某一指定的结点”是不确定的,你不能让一个指针指向2(例子中是2)。
于是,有了下面的思路。
思路一:
反转链表,反转时,会用到3个指针,分别为指向遍历时当前的结点的current指针,指向反转后的子链表的头结点的指针temp,及指向遍历时当前结点的下一个结点的next指针,如果在反转时,出现了next指向头结点的情况,那么肯定是有环的。
如:1->2->3->4->5->3,反转时,会有以下步骤:
①temp = NULL; current = 1; next = 2; 此时,反转生成的子链表:1->NULL
②temp = 1; current = 2; next = 3; 此时,反转生成的子链表:2->1->NULL
③temp = 2; current = 3; next = 4; 此时,反转生成的子链表:3->2->1->NULL
④temp = 3; current = 4; next = 2; 此时,反转生成的子链表:4->3->2->1->NULL
⑤temp = 4; current = 5; next = 3; 此时,反转生成的子链表:5->4->3->2->1->NULL
⑥temp = 5; current = 3; next = 2; 此时,反转生成的子链表:3->5->4->3 断开了 2->1->NULL
⑦temp = 3; current = 2; next = 1; 此时,反转生成的子链表:2->3->5->4->3 断开了 1->NULL
⑧判断到了next指向了头结点,说明有环。
代码为:
int is_cycle_list(Node* head) {
Node *temp, *current, *next;
if(!head)
return FALSE;
temp = NULL;
current = head;
next = head->next;
current->next = temp;
while(next) {
if(next == head) {
return TRUE;
}
temp = current;
current = next;
next = next->next;
current->next = temp;
}
return FALSE;
}
思路二:
用两个指针one_step,two_step,一块向后遍历,遍历时,one_step每次向后跳一步,two_step每次向后跳两步,直到two_step指向NULL,说明没有环(two_step肯定比one_step先到链表的尾部),或者两个指针都没有遍历到NULL结点,而两指针指向了同一结点,说明two_step赶上了one_step,此时肯定是有环的。
代码为:
int is_cycle_list(Node *list) {
Node *one_step, *two_step;
one_step = two_step = list;
if(!list) {
return FALSE;
}
while(two_step) {
one_step = one_step->next;
two_step = two_step->next;
if(!two_step) {
return FALSE;
}
two_step = two_step->next;
if(one_step == two_step) {
return TRUE;
}
}
return FALSE;
}
第一种方法反转了链表,需要再反转回来,才能还原到初始链表
扩展一下,如果判断到一个链表内部是有环的,如何找到从哪个结点开始,形成的环???
谁有好方法啊!!!!
分享到:
相关推荐
检查链表是否为空 5.检查链表是否为满 6.遍历链表(设为输出元素)7.从链表中查找元素 8.从链表中查找与给定元素值相同的元素在表中的位置 9.向链表中插入元素 10. 从链表中删除元素 其他键退出。。。。。 题目二 ...
链表删除环 alogcpp algorithm from leetcode and book base基础算法 clockangle 计算时钟的夹角 medianlist randomrange 变更随机数生成区间 //random5*5=> 0,5,10,15,20 //+random5 => 0,1,2,3,4,5,6...24 thread_...
检查链表是否为满 6.遍历链表(设为输出元素)7.从链表中查找元素 8.从链表中查找与给定元素值相同的元素在表中的位置 9.向链表中插入元素 10. 从链表中删除元素 其他键退出。。。。。 其中黑体部分必做
1.在一个双向链表中,删除任意一个结点...3.检查一个单链表中是否有环 4.已知链表的头结点head,写一个函数把这个链表逆序 约瑟夫环 5.循环链表--输入M,N值,从1至N开始顺序循环数数,每数到M输出该数值,直至全部输出
15. 如何检查二叉树是否是平衡的? 16. 什么是红黑树? 17. 如何合并两个排序的链表? 18. 描述快速排序算法的基本原理。 19. 解释什么是字典树(Trie)及其用途。 20. 如何找到一个数组的第K大元素? ### 中级知识...
1.1链表逆序1.2去除重复项1.3两链表表示的数字相加1.4链表从中间反转1.5遍历一次找到链表的倒数第k个中断1.6发现带环链表的环入口点1.7将单链表两两反转1.8单链表的前k个元素反转1.9合并两个单链表1.10从单链表中可...
必知必会:数据结构与算法 Algorithms + Data Structures = Programs ,— Niklaus Wirth目前而言,程序员的面试门生物学越来越高,很多一线互联网公司的技术面试,都或多或少会检查数据结构与算法相关的译文,掌握...
实例54多变的圆与环 实例55优美的球体 实例56运动的小车 实例57统计动画消失次数 实例58运行的时钟 实例59直升飞机 实例60演绎“生命游戏” 实例61猜猜看 买例62艺术清屏 买倒63制作火焰 实例...
实例54多变的圆与环 实例55优美的球体 实例56运动的小车 实例57统计动画消失次数 实例58运行的时钟 实例59直升飞机 实例60演绎“生命游戏” 实例61猜猜看 买例62艺术清屏 买倒63制作火焰 实例...
4.1 当errno为一个非零值时,是否有错误发生? 4.2 什么是流(stream)? 4.3 怎样重定向—个标准流? 4.4 怎样恢复一个重定向了的标准流? 4.5 stdout能被强制打印到非屏幕设备上吗? 4.6 文本模式(text mode...
写总结笔记,最好能整理思路,遇到相似题目可以写不出来代码,但要有完整思路 下一步 通过 或者 检查成果 没有思路的题目重点记录,进行下一阶段学习和总结 没法写出代码的,作为复习目标 其他计划 国外的教程 看...
│ 004 等待链表_调度链表.mp41 m! T& `3 t' U& U# A- @+ _ │ 005 模拟线程切换.mp4& ?, D% H/ z- d# _& \$ X- X$ U │ 006 Windows线程切换_主动切换.mp4 │ 007 Windows线程切换_时钟中断切换.mp4/ s& N% Y5 B" @...
-实现算法以检查数字是否为质数 -实施多套 -Cassandra使用的Murmur3哈希算法的实现 -灵活的Radix Tree实现 -基数树的实现 -三元搜索树 -文本算法的集合 Api建筑商 -使用Kemal创建RESTful API的库 区块链 -定制的...
实例097 计算字符串中有多少个单词 126 实例098 不使用strcpy()函数实现 字符串复制功能 127 实例099 逆序存放数据 129 实例100 相邻元素之和 130 实例101 选票统计 131 实例102 使用数组统计学生成绩 132 实例103 ...
对某交换类进行计费测试,字冠011对应1号路由、1号子路由,有4个中继群11,12,13,14(都属于1#模块),前后两个群分别构成自环。其中11,13群向为出中继,12,14群向为入中继,对这四个群分别进行计费设置,对出入中继都...
① 用函数 int IsNumberEqual(int number) 检查输入的整数number各数码是否互不相等,全相等返回值为1否则为0; ② 用函数(void ntos (int number, int c[]) )把四位数整数number各位数码分别存入数组c ③ 用函数( ...
空闲空间的管理方法主要有:空闲表法、空闲(自由)链表法、成组链接法 4、文件目录 (1)文件目录分类:一级文件目录、二级文件目录、多级文件目录 (2)文件目录的管理 •目录做成文件,文件...