C++ 判断链表是否成环
时间: 2023-10-02 15:08:42 浏览: 62
一般的做法是使用快慢指针,如果链表成环,快指针最终会追上慢指针,否则快指针会先达到链表尾部。
具体实现如下:
```c
bool hasCycle(ListNode *head) {
if (head == nullptr || head->next == nullptr) {
return false;
}
ListNode *slow = head;
ListNode *fast = head->next;
while (slow != fast) {
if (fast == nullptr || fast->next == nullptr) {
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
```
相关问题
python判断无向图节点成环
可以使用深度优先搜索(DFS)来判断无向图节点是否成环。具体步骤如下:
1. 初始化一个空的集合visited,用于记录已经遍历过的节点。
2. 对于无向图中的每个节点v,如果v不在visited集合中,则从v开始进行DFS遍历。
3. 在DFS遍历中,对于每个节点u,如果u不在visited集合中,则将u加入visited集合,并对u的所有未被访问过的邻居节点进行DFS遍历。
4. 在DFS遍历中,如果遇到一个已经在visited集合中的节点w,则说明无向图中存在环,返回True。
5. DFS遍历结束后,如果没有发现环,则返回False。
下面是使用Python实现的代码:
```python
def has_cycle(graph):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor == parent:
continue
if neighbor in visited:
return True
if dfs(neighbor, node):
return True
return False
for node in graph:
if node not in visited:
if dfs(node, None):
return True
return False
```
其中,graph是一个字典,表示无向图中每个节点的邻居节点。例如,对于无向图{(1, 2), (2, 3), (3, 1)},可以表示为{1: [2, 3], 2: [1, 3], 3: [1, 2]}。
C语言写一份成环检测算法
算法描述:
利用快慢指针判断一个链表是否成环,如果快指针能够追上慢指针,则链表存在环。
算法实现:
```
#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
int data;
struct Node* next;
}Node;
// 创建链表,返回头结点
Node* createList(int* arr, int n){
Node* head = (Node*)malloc(sizeof(Node));
head->data = -1;
head->next = NULL;
Node* p = head;
for(int i = 0; i < n; i++){
Node* node = (Node*)malloc(sizeof(Node));
node->data = arr[i];
node->next = NULL;
p->next = node;
p = p->next;
}
return head;
}
// 判断链表是否成环
int isCircle(Node* head){
Node* slow = head->next;
Node* fast = head->next;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
return 1;
}
}
return 0;
}
// 主函数
int main(){
int arr[] = {1,2,3,4,5};
int n = sizeof(arr)/sizeof(int);
Node* head = createList(arr, n);
//将链表的最后一个节点的指针指向第二个节点,形成环
Node* tail = head;
while(tail && tail->next){
tail = tail->next;
}
tail->next = head->next->next;
if(isCircle(head)){
printf("链表成环!\n");
}else{
printf("链表未成环!\n");
}
return 0;
}
```
算法解释:
该算法利用了快慢指针的特性,在遍历链表的过程中,慢指针每次向后移动一步,快指针每次向后移动两步,如果链表成环,那么快指针最终将追上慢指针。如果链表不成环,那么快指针最终将指向NULL,整个遍历过程将结束。