判断链表是否有环(两种方法)

我就是我 2022-08-08 06:13 191阅读 0赞

如何判断一个链表是否是一个循环链表呢?什么链表是一个循环链表?看图:

![20150507131008254][]

**一.步数比较法判断是否有环**

int HasLoop1(LinkList L){
    	LinkList cur1=L;//定义结点cur1
    	int pos1=0,pos2=0;
    	while(cur1){
    		pos2=0;//每次重设为0
    		LinkList cur2=L;
    		while(cur2){
    			if(cur2==cur1){
    				if(pos1==pos2)
    					break;//步数一样说明没有环
    				else{
    					printf("环的位置在第%d个结点处",pos2);
    					return 0;
    				}
    			}
    			pos2++;
    			cur2=cur2->next;
    		}
    		pos1++;
    		cur1=cur1->next;
    	}
    	return 0;
    }

![20150507132219490][]

**二.快慢指针判断:**

int HasLoop2(LinkList L){
    	int step1=1;
    	int step2=2;
    	LinkList p=L;
    	LinkList q=L;
    	
    	while(p!=NULL && q!=NULL && q->next!=NULL){
    		p=p->next;//p走一步
    
    		q=q->next->next;//q走两步
    		if(p==q)
    			return 1;
    	}
    	return 0;
    }

![20150507134439473][]

[20150507131008254]: /images/20220805/e0cb115f87b34e3880ce730cbf441fc0.png
[20150507132219490]: /images/20220805/9161f8b25ec243fa92393d2cfda5a0ec.png
[20150507134439473]: /images/20220805/009c6ebc685b4e29a0310836ad9bd37b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，191人围观）

还没有评论，来说两句吧...

相关阅读

相关判断链表是否有环

/ 判断链表是否有环快慢指针 / public class Test2 { public static void main(S

Love The Way You Lie/ 2022年10月29日 07:45/ 0 赞/ 206 阅读

相关判断链表是否有环

//判断链表是否有环 public static boolean IsLoop(Node head){ Node fast =

深碍√TFBOYSˉ_/ 2022年10月01日 05:50/ 0 赞/ 112 阅读

相关判断链表是否有环(两种方法)

如何判断一个链表是否是一个循环链表呢?什么链表是一个循环链表?看图: ![20150507131008254][] 一.步数比较法判断是否有环 int Ha

我就是我/ 2022年08月08日 06:13/ 0 赞/ 192 阅读

相关判断单链表是否有环的两种方法

如图，如果单链表有环，则在遍历时，在通过6之后，会重新回到3，那么我们可以在遍历时使用两个指针，看两个指针是否相等。 ![这里写图片描述][SouthEast] -----

朱雀/ 2022年07月11日 13:01/ 0 赞/ 174 阅读

相关判断链表是否有环

![这里写图片描述][70] //判断链表有环 public boolean hasCycle(ListNode head) {

忘是亡心i/ 2022年05月23日 04:42/ 0 赞/ 233 阅读

相关链表是否有环的两种判断方法

判断单链表是否有环假设有一个含环链表：1-2-3-4-5-6-3（6又连接到3，形成一个环） 1. 使用p、q两个指针，p总是向前走，但q每次都从头开始走，对

梦里梦外;/ 2022年05月16日 01:29/ 0 赞/ 180 阅读

相关判断链表是否有环？

题目描述有一个单向链表，链表当中有可能出现“环”，就像下图这样。如何用程序判断出这个链表是有环链表？ ![70][] 方法一：首先从头节点开始，依次遍历单链表的每

你的名字/ 2022年05月14日 03:56/ 0 赞/ 247 阅读

相关判断一个链表是否有环

判断一个链表是否有环方法一方法二方法三给出一个单向链表，判断链表中是否存在环。虽然是一个实际工作中基本不会碰到的场景，但是面试

骑猪看日落/ 2022年04月04日 14:27/ 0 赞/ 264 阅读

相关判断链表是否有环

给定一个单链表，只给出头指针h： 1、如何判断是否存在环？ 2、如何知道环的长度？ 3、如何找出环的连接点在哪里？ 4、带环链表的长度是多少？解法

素颜马尾好姑娘i/ 2022年03月25日 14:42/ 0 赞/ 308 阅读

相关判断单向链表是否有环

判断单链表是否有环问题汇总判断是否有环思路代码找出环的入口点思路

红太狼/ 2022年02月20日 08:12/ 0 赞/ 288 阅读