C语言/C++学习之C++中检测链表中的循环：本文主要总结了五个C++中检测链表中的循环的办法，通过具体的内容向大家展现，希望对C语言/C++的学习有所帮助。

给定一个链表，检查链表是否有循环。下图显示了带有循环的链表。

五个解决办法教你C++中检测链表中的循环

以下是执行此操作的不同方法

解决方案1：散列方法：

遍历该列表，并将节点地址始终放在哈希表中。在任何时候，如果达到NULL，则返回false，如果当前节点的下一个指向Hash中先前存储的任何节点，则返回true。

#include <bits/stdc++.h>

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<Node*> 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 << "Loop found";

    else

        cout << "No Loop";

    return 0;

}

复杂度分析：

时间复杂度： O（n）。

只需循环一次即可。

辅助空间： O（n）。

n是将值存储在哈希图中所需的空间。

解决方案2：通过修改链表数据结构，无需哈希图即可解决此问题。

方法：此解决方案需要修改基本链表数据结构。

每个节点都有一个访问标志。

遍历链接列表并继续标记访问的节点。

如果您再次看到一个访问过的节点，那么就会有一个循环。该解决方案适用于O（n），但每个节点都需要其他信息。

此解决方案的一种变体不需要修改基本数据结构，可以使用哈希来实现，只需将访问的节点的地址存储在哈希中，如果您看到哈希中已经存在的地址，则存在一个循环。

C++：

#include <bits/stdc++.h>

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 << "Loop found";

    else

        cout << "No Loop";

    return 0;

}

复杂度分析：

时间复杂度： O（n）。

只需循环一次即可。

辅助空间： O（1）。

不需要额外的空间。

解决方案3：Floyd的循环查找算法

方法：这是最快的方法，下面进行了介绍：

使用两个指针遍历链表。

将一个指针（slow_p）移动一个，将另一个指针（fast_p）移动两个。

如果这些指针在同一节点相遇，则存在循环。如果指针不符合要求，则链接列表没有循环。

Floyd的循环查找算法的实现：

#include <bits/stdc++.h>

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 << "Loop found";

    else

        cout << "No Loop";

    return 0;

}

解决方案4：在不修改链接列表数据结构的情况下标记访问的节点

在此方法中，将创建一个临时节点。使遍历的每个节点的下一个指针指向该临时节点。这样，我们将节点的下一个指针用作标志来指示该节点是否已遍历。检查每个节点以查看下一个节点是否指向临时节点。在循环的第一个节点的情况下，第二次遍历该条件将成立，因此我们发现该循环存在。如果遇到一个指向null的节点，则循环不存在。

下面是上述方法的实现：

#include <bits/stdc++.h>

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->key << " ";

        head = head->next;

    }

    cout << endl;

}

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 << "Loop Found";

    else

        cout << "No Loop";

    return 0;

}

复杂度分析：

时间复杂度： O（n）。

只需循环一次即可。

辅助空间： O（1）。

不需要空间。

解决方案5：存放长度

在此方法中，将创建两个指针，第一个（始终指向头）和最后一个指针。每次最后一个指针移动时，我们都会计算第一个和最后一个之间的节点数，并检查当前节点数是否大于先前的节点数，如果是，我们通过移动最后一个指针进行操作，否则就意味着我们已经到达循环的终点，因此我们相应地返回输出。

#include <bits/stdc++.h>

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->key << " ";

        head = head->next;

    }

    cout << endl;

}

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 << "Loop Found";

    else

        cout << "No Loop Found";

    return 0;

}

关注“职坐标在线”（Zhizuobiao_Online）公众号，免费获取学习视频资料、技术就业咨询