算法思路: 指针p1和p2的起始值均为链表的表头,指针p1每次走一步,指针p2每次走两步。如果链表存在环,则当p1和p2都进入环时,p2会“追上”p1,因为每次行走,p2和p1的距离都缩短了1.
//visual studio 2012 下编译通过
#include <stdio.h>
struct node{
int val;
node* next;
node(int val, node* next){
this->val = val;
this->next = next;
}
};
/*
* @brief 判断以head节点开头的单链表是否存在环, 时间复杂度是O(n),空间复杂度是O(1)
* @param node* head 链表的起始节点
*/
bool hasCircle(node* head){
node *p1, *p2;
p1 = p2 = head;
while(true){
if(p1 == NULL || p2 == NULL) return false;
p1 = p1->next;
p2 = p2->next;
if(p2 == NULL) return false;
p2 = p2->next;
if(p1 == p2) return true;
}
return true;
}
int main(){
//输入和输出重定向
freopen("in.txt","r", stdin);
freopen("out.txt", "w", stdout);
node *p1 = new node(1, NULL),
*p2 = new node(2, NULL),
*p3 = new node(3, NULL),
*p4 = new node(4, NULL);
/*
*case one
*/
p1->next = p2;
p2->next = p3;
p3->next = p4;
p4->next = p2;
if(hasCircle(p1)){
fprintf(stdout, "result of case one is yes \n");
}else{
fprintf(stdout, "result of case one is no \n");
}
/*
*case two
*/
p1->next = p2;
p2->next = p3;
p3->next = p4;
p4->next = NULL;
if(hasCircle(p1)){
fprintf(stdout, "result of case two is yes \n");
}else{
fprintf(stdout, "result of case two is no \n");
}
/*
*case three
*/
p1->next = p2;
p2->next = p3;
p3->next = p4;
p4->next = p1;
if(hasCircle(p1)){
fprintf(stdout, "result of case three is yes \n");
}else{
fprintf(stdout, "result of case three is no \n");
}
}
分享到:
相关推荐
笔试时,常见的题型。判断单链表中是否存在环
在Java中,判断单链表是否有环的经典方法是使用Floyd的“龟兔赛跑”算法,也称为快慢指针法。这种方法利用两个指针,一个每次走一步(称为慢指针),另一个每次走两步(称为快指针)。如果链表中存在环,那么快指针...
附件是使用双指针发判断链表有环的代码实现,在Java中,判断单链表是否有环的经典方法是使用Floyd的“龟兔赛跑”算法,也称为快慢指针法。这种方法利用两个指针,一个每次走一步(称为慢指针),另一个每次走两步...
8.判断单链表是否有环?如何找到环的“起始”点?如何知道环的长度? 9.判断两个单链表是否相交 10.两个单链表相交,计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素
判断单链表是否有环?如何找到环的“起始”点?如何知道环的长度? 9.判断两个单链表是否相交 10.两个单链表相交,计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素
@不了解前尘往事的Reader,烦请阅读——《判断单链表是否有环的算法》 如何找带环单链表的环的入口 这里只说比较可行的算法吧。 思路一:HashSet第一个重复元素就是环的入口 按照查找单链表带环的思路二,我们用一个...
通过Java实现单链表的操作,包括单链表定义、遍历、置空、判空、插入、删除、反转、中间结点、指定顺序排序、前插、后插、判断单链表是否存在环、环的长度、环的起始结点
判断单链表是否有环 二分搜索 缺失的数字 包含min函数的栈 合并两个递增排序的链表 连续子序列的最大和 替换空格 二维数组中的查找 从尾到头打印链表 重建二叉树(用前序和中序构建) 从上到下打印二叉树(层序遍历) ...
8. 找出链表的倒数第四个节点9. 找出链表的中间节点10. 判断单链表是否有环11. 判断两个链表是否相交, 如果相交, 计算交点12. 删除单链表中重复的元
代码中包含单链表的常用操作,主要实现以下六个算法: 1.单链表的就地反转 2.链表相交或求公共起始节点 3.求链表倒数第n个节点 ...5.判断链表是否有环 6.将2个递增的链表合并为递减链表 并全部调试通过。
判断两个有环链表是否相交,相交则返回第一个相交节点,否则返回null 在考虑此问题时,根据前面几篇文章的解法,我们已经得到了各自链表的入环节点,分别为loop1和loop2 思路 以下是问题三的具体解决过程: 如果loop...
判断单链表是否有环,快慢指针 单链表有环的情况下,找到环中的第一个节点 合并两个有序链表,保证新的链表也是有序的,递归或者迭代 合并K个有序链表,先写合并2个,然后逐个合并 链表排序,涉及归并排序、快慢指针...
[判断单链表是否有环] [ES中对象在底层的储存方式,ES6 MAP/SET在底层是否采用hashmap/红黑树存储? EnumerateObjectProperties EnumerableOwnProperties] [最长上升子序列] # 1. 求两个已排序数组的中位数 There ...
包括如下操作:初始化、销毁、清空、求长度、遍历 指定位置插入和删除元素 按位置和按元素值查找 查找并删除单链表中值域为e的全部结点 ... 建环/判断环存在 删除重复元素 合并两种有序单链表
根据链表数据结构的知识,进行初步练习,从单链表的反转、环的检测、两个有序链表的合并、判断单向链表是否是回文字符串四个题目着手,分别进行代码实现。 首先定义单链表类: # 结点类 class Node(object): def _...
linkedListjava单链表的实现和简单操作注意isCircle()这个函数是判断单链表是否成环的函数,由于是单链表所以头尾指针只有一个,所以出现环只能是大圈,最后一个和头结点成环,不可能出现中间“打结”的情况,我们...
java lru leetcode algorithm 《数据结构与算法之美》练习 ...判断链表中是否有环。如果有环求入口节点 Floyd法。先用快慢指针确定是否有环。如果有环找出相遇点。分别从相遇点和头节点出发,再次相遇时即是
二叉树的层次遍历及宽度,哈夫曼树,将L中的整数序列循环左移p个位置,将表L中所有值为x 的元素删除,判断链表中是否存在环,删除单链表L(L中元素值各不相同)的最大值所对应的结点,并返回该值,树的孩子兄弟表示...
判断一个单链表中,是否存在环。采用双指针,一快一慢,判断两指针在多次迭代后,是否相遇。即龟兔算法。
2、写一段代码判断单向链表中有没有形成环,如果形成环,请找出环的入口处,即P点 /* *单链表的结点类 */ class LNode{ //为了简化访问单链表,结点中的数据项的访问权限都设为public public int data; public ...