如何判断一个链表有环
时间: 2024-04-26 18:26:43 浏览: 9
当判断一个链表是否有环时,可以使用快慢指针法。假设链表中存在环,那么用两个指针,快指针每次移动两步,慢指针每次移动一步。如果链表中没有环,快指针会先到达链表尾部。如果链表中有环,快指针最终会追上慢指针,两个指针会相遇。因此,通过判断两个指针是否相遇,即可确定链表是否有环。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [【算法】如何判断链表有环](https://blog.csdn.net/u010983881/article/details/78896293)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]
相关问题
C语言判断一个链表是否有环
要判断一个链表是否有环,可以使用快慢指针的方法。
快指针每次移动两个节点,慢指针每次移动一个节点,如果链表中存在环,那么快指针和慢指针一定会在环内某个节点相遇。
以下是示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 判断链表是否有环
int hasCycle(ListNode *head) {
if (head == NULL) {
return 0;
}
ListNode *slow = head;
ListNode *fast = head->next;
while (fast != NULL && fast->next != NULL) {
if (slow == fast) {
return 1;
}
slow = slow->next;
fast = fast->next->next;
}
return 0;
}
// 创建链表
ListNode* createList(int* nums, int numsSize) {
if (numsSize == 0) {
return NULL;
}
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->val = nums[0];
head->next = NULL;
ListNode *cur = head;
for (int i = 1; i < numsSize; i++) {
ListNode *node = (ListNode*)malloc(sizeof(ListNode));
node->val = nums[i];
node->next = NULL;
cur->next = node;
cur = node;
}
return head;
}
int main() {
int nums[] = {1, 2, 3, 4, 5};
int numsSize = 5;
ListNode *head = createList(nums, numsSize);
// 将链表尾部指向第二个节点,构成一个环
head->next->next->next->next->next = head->next;
int result = hasCycle(head);
printf("result: %d\n", result);
return 0;
}
```
输出结果为1,表示链表中存在环。
如何判断一个链表是否存在环
判断一个链表是否存在环,可以使用快慢指针的方法。具体地,使用两个指针,一个慢指针 slow 和一个快指针 fast,初始时都指向链表的头节点。然后,每次让 slow 指针向后移动一个位置,fast 指针向后移动两个位置,如果存在环,那么它们最终一定会相遇,否则,fast 指针会先到达链表的末尾,此时可以判断链表不含环。
以下是使用 Python 语言实现的代码:
```python
def has_cycle(head):
if not head or not head.next:
return False
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
```
在代码中,我们首先做了一些边界处理,如果链表为空或只有一个节点,那么肯定不存在环,直接返回 False。接着,我们使用快慢指针进行遍历。由于 fast 指针每次向后移动两个位置,所以如果链表中有环,fast 指针一定会经过这个环,而 slow 指针最终也会进入这个环,最终它们会相遇。如果 fast 指针先到达链表的末尾,那么链表肯定不含环,返回 False。