是技术,更是艺术

一心编程,就没有解决不了的问题
posts - 9, comments - 11, trackbacks - 0, articles - 0

判断单链表是否有环

Posted on 2010-09-24 12:30 李熙建 阅读(3143) 评论(4)  编辑 收藏 引用 所属分类: C++

 

typedef struct LNode
{
    
int data;
    LNode 
*next;
}
LNode ;
typedef LNode
* LinkList;
//单链表有环返回true 否则返回false
bool is_looplist(LNode *head)
{
    LNode 
*fast,*slow;
    
if (head == NULL || head->next == NULL)
    
{
        
return false;
    }

    
slow = head;fast = head->next;

    
while(true)
    
{
        
if(!fast || !fast->next)
            
return false;
        
//为了防止fast跨过slow的情况,在每次判断的时候比较当前节点和下一节点
        else if (fast == slow || fast->next == slow)
            
return true;
        
else
        
{
            slow 
= slow->next;//一次跳一步
            fast = fast->next->next;//一次跳两步
        }

    }

}

如果要返回环的入口节点
一种效率比较低的方法是
一个指针p1从表头开始,指针p2 初始化为判环时找到的指针,p1每前进一步,由p2遍历一次环中各结点,遍历过程中每次都要判断p1是否p2
当p2 == fast时候,p1 = p1.next,继续循环。这样肯定能找到入口,但是效率为O(n^2)

Feedback

# re: 判断单链表是否有环  回复  更多评论   

2010-09-25 08:16 by Algorics
如果知道链表的结点数n,那么如果进行n+1次找下一个结点还没到链表的尾部的话就有环。

# re: 判断单链表是否有环  回复  更多评论   

2010-09-26 21:46 by 李熙建
@Algorics
一般情况下,只已知链表的头节点,链表元素个数已知的情况下,你说的方法可以

# re: 判断单链表是否有环[未登录]  回复  更多评论   

2011-05-06 17:49 by kyle
代码有错...永远返回TRUE.
在对fast初始化的时候应该是fast=head->next;

# re: 判断单链表是否有环  回复  更多评论   

2011-08-01 09:14 by 李熙建
@kyle
非常感谢你指出其中的错误

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理