环形链表(快慢指针)

简介: 环形链表(快慢指针)

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false

#include <stdbool.h>
struct ListNode {
    int val;
    struct ListNode *next;
};
bool hasCycle(struct ListNode *head) {
    if (!head || !head->next) {
        return false; // 链表为空或只有一个节点,肯定没有环
    }
    struct ListNode *slow = head;
    struct ListNode *fast = head->next;
    while (slow != fast) {
        if (!fast || !fast->next) {
            return false; // 如果快指针或快指针的下一个节点为NULL,说明没有环
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return true; // 如果能跳出循环,说明有环
}

这里同样使用了快慢指针的方法,注意在C语言中要使用 struct 来定义链表节点。算法思想和Python版本相同,只是语法有所不同。

如果你想测试上述 C 代码,可以创建一个简单的链表,并手动设置环。以下是一个例子:

#include <stdio.h>
#include <stdbool.h>
struct ListNode {
    int val;
    struct ListNode *next;
};
bool hasCycle(struct ListNode *head);
int main() {
    // 创建链表:1 -> 2 -> 3 -> 4 -> 5 -> 2(与节点3相同,形成环)
    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    head->val = 1;
    struct ListNode *node2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    node2->val = 2;
    head->next = node2;
    struct ListNode *node3 = (struct ListNode *)malloc(sizeof(struct ListNode));
    node3->val = 3;
    node2->next = node3;
    struct ListNode *node4 = (struct ListNode *)malloc(sizeof(struct ListNode));
    node4->val = 4;
    node3->next = node4;
    struct ListNode *node5 = (struct ListNode *)malloc(sizeof(struct ListNode));
    node5->val = 5;
    node4->next = node5;
    // 设置环
    node5->next = node2;
    // 测试是否有环
    if (hasCycle(head)) {
        printf("链表中存在环。\n");
    } else {
        printf("链表中不存在环。\n");
    }
    // 释放节点内存
    free(head);
    free(node2);
    free(node3);
    free(node4);
    free(node5);
    return 0;
}

在这个例子中,我们手动创建了一个包含五个节点的链表,并设置第五个节点指向第二个节点,形成了一个环。当运行程序时,输出应该是 "链表中存在环"。

 

相关文章
|
7天前
|
索引
【力扣】142. 环形链表 II
【力扣】142. 环形链表 II
|
7天前
|
C语言 C++ 索引
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
|
7天前
数据结构--链表刷题(一)快慢指针(下)
数据结构--链表刷题(一)快慢指针
16 0
|
7天前
数据结构--链表刷题(一)快慢指针(上)
数据结构--链表刷题(一)快慢指针
18 0
|
7天前
|
存储 编译器 C语言
【数据结构】深入浅出理解链表中二级指针的应用
【数据结构】深入浅出理解链表中二级指针的应用
33 0
|
7天前
|
算法 Java
快慢指针该如何操作?本文带你认识快慢指针常见的三种用法及在链表中的实战
快慢指针该如何操作?本文带你认识快慢指针常见的三种用法及在链表中的实战
29 0
|
7天前
|
存储 算法
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)
|
1天前
|
存储 编译器 C语言
C语言内功修炼--指针详讲(进阶)
C语言内功修炼--指针详讲(进阶)
|
1天前
|
存储 C语言
C语言内功修炼---指针详讲(初阶)
C语言内功修炼---指针详讲(初阶)
|
1天前
|
存储 编译器 程序员
从C语言到C++④(第二章_类和对象_上篇)->类->封装->this指针(下)
从C语言到C++④(第二章_类和对象_上篇)->类->封装->this指针
4 0