是技术，更是艺术

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

判断单链表是否有环

Posted on 2010-09-24 12:30 李熙建 阅读(3160) 评论(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   博问   Chat2DB   管理