五个解决办法教你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 << "Loop found"; 
  
  
      else 
  
  
          cout << "No Loop"; 
  
  
    
  
  
      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 << "Loop found"; 
  
  
      else 
  
  
          cout << "No Loop"; 
  
  
    
  
  
      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 << "Loop found"; 
  
  
      else 
  
  
          cout << "No Loop"; 
  
  
      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->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  
  
  
  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; 
  
  
  }

}

当前题目：五个解决办法教你C++中检测链表中的循环
标题链接：http://www.hnjierui.cn/article/dpdoepe.html

网站建设资讯

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

其他资讯