当前位置：极客教程 > C++语言 > C++ 示例 > C++程序 检测链表中的循环

C++程序 检测链表中的循环

C++程序 检测链表中的循环

给定一个链表，检查它是否存在循环。下面的图示展示了带有循环的链表。

C++程序 检测链表中的循环

以下是不同的实现方法。

解法 1：哈希方法：

逐一遍历列表，将节点地址放入哈希表中。若到达 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 this node is already present
        // in hashmap it means there is a cycle
        // (Because you we encountering the
        // node for the 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;
}
 
/* Driver 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;
}
// This code is contributed by Geetanjali```

输出

Loop found

复杂度分析：

  • 时间复杂度： 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;
}

// 如果链表中存在循环，返回true；否则返回false
bool detectLoop(struct Node* h){
    while (h != NULL){
        // 如果遇到已经遍历过的节点
        // 这意味着链表中有一个循环
        // （因为你第二次遇到了节点）。
        if (h->flag == 1)
            return true;

        // 如果我们第一次遇到这个节点，则将其标记为1
        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;
}
// 本代码由Geetanjali贡献```

输出

Loop found

复杂度分析：

  • 时间复杂度： O (n)。 仅需要一次遍历循环。
  • 辅助空间： O (1)。 不需要额外的空间。

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

方法： 这是最快的方法，如下所述：

  • 使用两个指针遍历链表。
  • 将一个指针（slow_p）移动一步，另一个指针（fast_p）移动两步。
  • 如果这些指针在同一节点相遇，则存在循环。如果指针不相遇，则链表没有循环。

以下图像显示了代码中的detectloop函数的工作方式：

C++程序 检测链表中的循环

Floyd循环查找算法的实现：

// C++程序检测链表中的循环
#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 << "循环存在";
    else
        cout << "没有循环";
    return 0;
}
 
// 本代码由rathbhupendra提供```

输出

循环存在

时间/空间复杂度分析:

  • 时间复杂度: O(n)。 只需要一次遍历循环。
  • 空间复杂度: O(1)。 不需要额外空间。

解决方案4：标记访问但不修改链接列表结构的节点

在此方法中，创建一个临时节点。将要遍历的每个节点的下一个指针指向此临时节点。通过这种方式，我们使用节点的下一个指针作为标志来指示节点是否已遍历。检查每个节点以查看下一个指向临时节点还是不指向。对于循环的第一个节点，在第二次遍历它时，这个条件将为真，因此我们发现存在循环。如果遇到指向空的节点，则不存在循环。

以下是上述方法的实现：

// C++程序返回循环链表的第一个节点
#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->key << " ";
        head = head->next;
    }
    cout << endl;
}
 
// 检测在可能包含循环的链表中的第一个节点的函数
bool detectLoop(Node* head){
    // 创建一个临时节点
    Node* temp = new Node;
    while (head != NULL){
        // 这个条件是为了不存在循环的情况
        if (head->next == NULL){
            return false;
        }
        // 检查下一个是否已经指向temp
        if (head->next == temp){
            return true;
        }
        // 存储指向下一个节点的指针，以便在下一步中访问它
        Node* nex = head->next;
        // 将下一个指向temp
        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);
    /* 创建一个用于测试的循环（5指向3）*/
    head->next->next->next->next->next = head->next->next;
    bool found = detectLoop(head);
    if (found){
        cout << "Loop Found";
    }
    else{
        cout << "No Loop";
    }
    return 0;
}

输出

Loop Found

复杂度分析：

  • 时间复杂度： O(n)。 只需要一次遍历循环。
  • 辅助空间： O(1)。 不需要额外的空间。

解决方案5：存储长度

在此方法中，创建两个指针，第一个始终指向头，第二个始终指向末尾。每次最后一个指针移动时，我们计算第一个和最后一个之间的节点数，并检查当前节点数是否大于先前节点数，如果是，则进行下一步移动最后一个指针，否则它意味着我们已经到达了循环的结尾，因此返回相应的输出。

//C++程序，用于返回循环的第一个节点
#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->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*/
    first = head;
    /*last指针最初指向head*/
    last = head;
 
    /*current_length存储当前
     * first和last之间的节点数*/
    int current_length = 0;
 
    /*prev_length存储上一个
     * first和last之间的节点数*/
    int prev_length = -1;
 
    while (current_length > prev_length && last != NULL) {
        //将prev_length设置为current_length，然后更新当前长度
          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);
 
    /* Create a loop for testing(5 is pointing to 3) */
    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;
}

输出

Loop Found

复杂度分析：

  • 时间复杂度： O(n2)
  • 辅助空间： O(1)

其他方法：

  1. 这是给定问题的最简单方法，我们所要做的就是为链接列表中每个节点的数据分配一个新值，该值不在给定范围内。
  2. 例如，假设(1<=Data on Node<=10^3)，则在访问节点后，将数据分配为-1，因为它超出了给定范围。

请按以下给出的代码进行更好的理解：

// C++程序以返回循环的第一个节点
#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;
}
 
// 检测可能包含循环的链表中的第一个循环节点的函数
bool detectLoop(Node* head)
{
     
    // 如果head为空，我们将返回false
    if (!head)
        return 0;
    else {
       
        // 遍历链表以检测循环
        while (head) {
            // 如果找到循环
            if (head->key == -1) {
                return true;
            }
           
            // 将已访问节点的数据更改为任何一个
            // 在给定范围之外的值，这里假设在
            // 给定范围为(1 <= 节点数据 <= 10^3)
            else {
                head->key = -1;
                head = head->next;
            }
        }
        // 如果未找到循环则返回false
        return 0;
    }
}
 
/* 主程序用于测试上述函数 */
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);
 
    /* 用于测试循环的创建（5指向3） */
    head->next->next->next->next->next = head->next->next;
 
    bool found = detectLoop(head);
    cout << found << endl;
    return 0;
}

输出

1

时间复杂度: O(N)

辅助空间: O(1)

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

C++ 示例