环状链表判断算法

判断该链表是否有环

采用两个指针，一个用来遍历，一个用来从头到当前遍历位置的数据对比。
思想：比较元素是否出过；
复杂度：时间O(n^2),空间O(1)
hash表的方法，记录元素，一旦在hash表中出现过,就证明有环
复杂度：时间O(n),空间O(n)
双指针类型方法：两个指针p1和p2，让它们同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针p1每次向后移动1个节点，让指针p2每次向后移动2个节点，然后比较
两个指针指向的节点是否相同。如果相同，则可以判断出链表有环，如果不同，则继续下一次循环。
思想：追及问题，让快的先跑，如果有环，快的绕一圈后肯定会追上慢的。
复杂度：时间O(n),空间O(1)

#include<iostream>
using namespace std;

struct node{
 int value;
 node *next;
 node(int a):value(a),next(NULL){}
};
typedef node list;
bool iscycle(list * head){
    node *p1,*p2;
    p1 = head;
    p2= head;
    while(p1!=NULL&&p1->next!=NULL) //因为p1每次走两步，所以需要判断一下最后两个是否为空，以便决定是否循环；
    {
        p1 = p1->next->next;
        p2 = p2->next;
        if(p1==p2)
        {
            return 1;
        }
    }
    return 0;
}
int main()
{

 node * node1 = new node(5);
 node * node2 = new node(3);
 node * node3 = new node(7);
 node * node4 = new node(2);
 node * node5 = new node(6);
 node1->next = node2;
 node2->next = node3;
 node3->next = node4;
 node4->next = node5;
 node5->next = node2;
 //cout << node5->next << endl;
 cout << iscycle(node1) << endl;
}

如何求出环的长度？

当两个指针首次相遇，证明链表有环的时候，让两个指针从相遇点继续循环前进，并统计前进的循环次数，直到两个指针第2次相遇。此
时，统计出来的前进次数就是环长。
因为指针p1每次走1步，指针p2每次走2步，两者的速度差是1步。当两个指针再次相遇时，p2比p1多走了整整1圈。
因此，环长 = 每一次速度差 × 前进次数 = 前进次数
也就是环长=1×前进次数

如何求出入环节点？

如果链表有环，如何求出入环节点？
答：只要把其中一个指针放回到头节点位置，另一个指针保持在首次相遇点，两个指针都是每次向前走1步。那么，它们最终相遇的节点，就是入环节点。
以上答案根据一个走两步一个走一步计算出的。

参考资料

漫画算法

# 算法, 链表

目录

链接

分类

标签云

最新文章

归档

标签

环状链表判断算法

判断该链表是否有环

如何求出环的长度？

如何求出入环节点？

参考资料

喜欢这篇文章？打赏一下作者吧

评论

Your browser is out-of-date!