指定一个链表, 判断其中是否存在循环。下面的图表表示链表中存在一个循环。
下面用两种不同方法来实现
使用哈希:
顺序遍历链表，把结点地址放在一个哈希表中。任何时候, 如果地址为 NULL 表示链表到头，就返回 false, 如果当前结点的后继结点地址跟哈希表里的某个地址相同就返回 true.
// C++ program to detect loop in a linked list
#include<bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = new Node;
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Returns true if there is a loop in linked list
// else returns false.
bool detectLoop(struct Node *h)
{
unordered_set<Node *> s;
while (h != NULL)
{
// If we have already has this node
// in hashmap it means their is a cycle
// (Because you we encountering the
// node second time).
if (s.find(h) != s.end())
return true;
// If we are seeing the node for
// the first time, insert it in hash
s.insert(h);
h = h->next;
}
return false;
}
/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
/* Create a loop for testing */
head->next->next->next->next = head;
if (detectLoop(head))
cout << "Loop found";
else
cout << "No Loop";
return 0;
}
输出 :
Loop Found
标记访问过的结点:
这个方案需要修改链表的数据结构。每个结点有个 visited 标记。遍历整个链表，标记所有访问过的结点。如果你再次看见访问过的结点，就表明存在一个循环。这个方案的时间复杂度是 O(n), 但是每个结点需要额外的信息。
这个方案可以修改成不修改链表的数据结构, 然后使用哈希来实现。仅仅是把访问过的结点地址放进哈希表，如果发现后面访问的地址在哈希表里存在，就表示有循环存在。
循环查找算法:
这是个最快的方法。使用两个指针进行遍历。一个指针每次向前移动一步，另外一个指针移动两步。如果这两个指针在某个结点相遇，就表明存在一个循环。如果指针不相遇就表明链表不存在循环。
循环查找算法的实现:
// C program to detect loop in a linked list
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
int detectloop(struct Node *list)
{
struct 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)
{
printf("Found Loop");
return 1;
}
}
return 0;
}
/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
/* Create a loop for testing */
head->next->next->next->next = head;
detectloop(head);
return 0;
}
输出:
Found loop