C＋丨如何检查链表中的循环？这5个方案，真是太绝了！
通过5个解决方案教你C++中检测链表中的循环，快来看看，是否对你有帮助！
给定一个链表，检查链表是否有循环。下图显示了带有循环的链表。
以下是执行此操作的不同方法
解决方案1：散列方法
遍历该列表，并将节点地址始终放在哈希表中。在任何时候，如果达到NULL，则返回false，如果当前节点的下一个指向Hash中先前存储的任何节点，则返回true。
#include?
using?namespace?std;
struct?Node?{
int?data;
struct?Node*?next;
};
void?push(struct?Node**?head_ref,?int?new_data)
{
struct?Node*?new_node?=?new?Node;
new_node->data?=?new_data;
new_node->next?=?(*head_ref);
(*head_ref)?=?new_node;
}
bool?detectLoop(struct?Node*?h)
{
unordered_set?s;
while?(h?!=?NULL)?{
if?(s.find(h)?!=?s.end())
return?true;
s.insert(h);
h?=?h->next;
}
return?false;
}
int?main()
{
struct?Node*?head?=?NULL;
push(&head,?20);
push(&head,?4);
push(&head,?15);
push(&head,?10);
head->next->next->next->next?=?head;
if?(detectLoop(head))
cout?
else
cout?
return?0;
}
复杂度分析：
时间复杂度：O（n）。
只需循环一次即可。
辅助空间：O（n）。
n是将值存储在哈希图中所需的空间。
解决方案2：通过修改链表数据结构，无需哈希图即可解决此问题。
方法：此解决方案需要修改基本链表数据结构。
每个节点都有一个访问标志。
遍历链接列表并继续标记访问的节点。
如果您再次看到一个访问过的节点，那么就会有一个循环。该解决方案适用于O（n），但每个节点都需要其他信息。
此解决方案的一种变体不需要修改基本数据结构，可以使用哈希来实现，只需将访问的节点的地址存储在哈希中，如果您看到哈希中已经存在的地址，则存在一个循环。
C++：
#include?
using?namespace?std;
struct?Node?{
int?data;
struct?Node*?next;
int?flag;
};
void?push(struct?Node**?head_ref,?int?new_data)
{
struct?Node*?new_node?=?new?Node;
new_node->data?=?new_data;
new_node->flag?=?0;
new_node->next?=?(*head_ref);
(*head_ref)?=?new_node;
}
bool?detectLoop(struct?Node*?h)
{
while?(h?!=?NULL)?{
if?(h->flag?==?1)
return?true;
h->flag?=?1;
h?=?h->next;
}
return?false;
}
int?main()
{
struct?Node*?head?=?NULL;
push(&head,?20);
push(&head,?4);
push(&head,?15);
push(&head,?10);
head->next->next->next->next?=?head;
if?(detectLoop(head))
cout?
else
cout?
return?0;
}
复杂度分析：
时间复杂度：O（n）。
只需循环一次即可。
辅助空间：O（1）。
不需要额外的空间。
解决方案3：Floyd的循环查找算法方法
这是最快的方法，下面进行了介绍。
使用两个指针遍历链表。
将一个指针（slow_p）移动一个，将另一个指针（fast_p）移动两个。
如果这些指针在同一节点相遇，则存在循环。如果指针不符合要求，则链接列表没有循环。
Floyd的循环查找算法的实现：
#include?
using?namespace?std;
class?Node?{
public:
int?data;
Node*?next;
};
void?push(Node**?head_ref,?int?new_data)
{
Node*?new_node?=?new?Node();
new_node->data?=?new_data;
new_node->next?=?(*head_ref);
(*head_ref)?=?new_node;
}
int?detectLoop(Node*?list)
{
Node?*slow_p?=?list,?*fast_p?=?list;
while?(slow_p?&&?fast_p?&&?fast_p->next)?{
slow_p?=?slow_p->next;
fast_p?=?fast_p->next->next;
if?(slow_p?==?fast_p)?{
return?1;
}
}
return?0;
}
int?main()
{
Node*?head?=?NULL;
push(&head,?20);
push(&head,?4);
push(&head,?15);
push(&head,?10);
head->next->next->next->next?=?head;
if?(detectLoop(head))
cout?
else
cout?
return?0;
}
解决方案4：在不修改链接列表数据结构的情况下标记访问的节点
在此方法中，将创建一个临时节点。使遍历的每个节点的下一个指针指向该临时节点。这样，我们将节点的下一个指针用作标志来指示该节点是否已遍历。检查每个节点以查看下一个节点是否指向临时节点。在循环的第一个节点的情况下，第二次遍历该条件将成立，因此我们发现该循环存在。如果遇到一个指向null的节点，则循环不存在。
下面是上述方法的实现：
#include?
using?namespace?std;
struct?Node?{
int?key;
struct?Node*?next;
};
Node*?newNode(int?key)
{
Node*?temp?=?new?Node;
temp->key?=?key;
temp->next?=?NULL;
return?temp;
}
void?printList(Node*?head)
{
while?(head?!=?NULL)?{
cout?
head?=?head->next;
}
cout?
}
bool?detectLoop(Node*?head)
{
Node*?temp?=?new?Node;
while?(head?!=?NULL)?{
if?(head->next?==?NULL)?{
return?false;
}
if?(head->next?==?temp)?{
return?true;
}
Node*?nex?=?head->next;
head->next?=?temp;
head?=?nex;
}
return?false;
}
int?main()
{
Node*?head?=?newNode(1);
head->next?=?newNode(2);
head->next->next?=?newNode(3);
head->next->next->next?=?newNode(4);
head->next->next->next->next?=?newNode(5);
head->next->next->next->next->next?=?head->next->next;
bool?found?=?detectLoop(head);
if?(found)
cout?
else
cout?
return?0;
}
复杂度分析：
时间复杂度：O（n）。
只需循环一次即可。
辅助空间：O（1）。
不需要空间。
解决方案5：存放长度
在此方法中，将创建两个指针，第一个（始终指向头）和最后一个指针。每次最后一个指针移动时，我们都会计算第一个和最后一个之间的节点数，并检查当前节点数是否大于先前的节点数，如果是，我们通过移动最后一个指针进行操作，否则就意味着我们已经到达循环的终点，因此我们相应地返回输出。
#include?
using?namespace?std;
struct?Node?{
int?key;
struct?Node*?next;
};
Node*?newNode(int?key)
{
Node*?temp?=?new?Node;
temp->key?=?key;
temp->next?=?NULL;
return?temp;
}
void?printList(Node*?head)
{
while?(head?!=?NULL)?{
cout?
head?=?head->next;
}
cout?
}
int?distance(Node*?first,?Node*?last)
{
int?counter?=?0;
Node*?curr;
curr?=?first;
while?(curr?!=?last)?{
counter?+=?1;
curr?=?curr->next;
}
return?counter?+?1;
}
bool?detectLoop(Node*?head)
Node*?temp?=?new?Node;
Node?*first,?*last;
first?=?head;
last?=?head;
int?current_length?=?0;
int?prev_length?=?-1;
while?(current_length?>?prev_length?&&?last?!=?NULL)?{
prev_length?=?current_length;
current_length?=?distance(first,?last);
last?=?last->next;
}
if?(last?==?NULL)?{
return?false;
}
else?{
return?true;
}
}
int?main()
{
Node*?head?=?newNode(1);
head->next?=?newNode(2);
head->next->next?=?newNode(3);
head->next->next->next?=?newNode(4);
head->next->next->next->next?=?newNode(5);
head->next->next->next->next->next?=?head->next->next;
bool?found?=?detectLoop(head);
if?(found)
cout?
else
cout?
return?0;
}
感谢阅读，希望能帮助到大家，有什么问题欢迎评论区留言。
- 发表于:
- 原文链接：https://kuaibao.qq.com/s/20201227A09MUF00?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
