温馨提示×

如何检测C++单链表中的循环引用

c++
小樊
84
2024-07-16 20:17:47
栏目: 编程语言

检测C++单链表中的循环引用可以使用快慢指针法。假设链表中有一个快指针和一个慢指针,快指针每次移动两步,慢指针每次移动一步。如果存在循环引用,那么快指针和慢指针最终会在循环中相遇。

具体步骤如下:

  1. 定义一个快指针和一个慢指针,初始位置都指向链表的头节点。
  2. 每次循环中,快指针先移动两步,慢指针移动一步。
  3. 检查快指针是否遇到了NULL,如果遇到了就说明链表中不存在循环引用。
  4. 如果快指针和慢指针相遇,则说明链表中存在循环引用。

以下是一个示例代码:

bool hasCycle(ListNode* head) {
    if(head == NULL) {
        return false;
    }
    
    ListNode* slow = head;
    ListNode* fast = head->next;
    
    while(fast != NULL && fast->next != NULL) {
        if(slow == fast) {
            return true;
        }
        
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return false;
}

在上面的代码中,我们定义了一个快指针fast和一个慢指针slow,它们分别移动一步和两步。如果存在循环引用,快指针和慢指针最终会相遇并返回true,否则返回false。

0