【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)

简介: 【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)

题目描述

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos-1,则在该链表中没有环。

示例 1

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

原题:Leetcode 141. 环形链表

思路及实现

方式一:快慢指针

思路

快慢指针是解决链表环问题的一个常见技巧。在这个方法中,我们设置两个指针,一个快指针(每次移动两步)和一个慢指针(每次移动一步)。如果链表中存在环,那么快指针最终会追上慢指针,即两者会在某个节点相遇;如果链表中没有环,那么快指针会先到达链表尾部(null)。

代码实现

Java版本
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return true;
    }
}

说明:

  • 首先检查链表是否为空或只有一个节点,如果是,则肯定没有环。
  • 初始化慢指针 slow 指向头节点,快指针 fast 指向头节点的下一个节点。
  • 进入循环,如果快指针或快指针的下一个节点为空,则链表中没有环。
  • 否则,慢指针每次移动一步,快指针每次移动两步,直到两者相遇或快指针到达链表尾部。
C语言版本
struct ListNode {
    int val;
    struct ListNode *next;
};
bool hasCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    
    struct ListNode *slow = head;
    struct ListNode *fast = head->next;
    
    while (slow != fast) {
        if (fast == NULL || fast->next == NULL) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return true;
}

说明:

  • C语言版本的实现与Java版本类似,只是语法和类型定义有所不同。
Python3版本
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        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

说明:

  • Python版本的实现也遵循同样的逻辑,使用类来定义链表节点,并在Solution类中实现hasCycle方法。

复杂度分析

  • 时间复杂度:O(n),其中n是链表的长度。在链表有环的情况下,快指针每次移动两步,因此最坏情况下需要遍历链表长度的一半;

在链表没有环的情况下,快指针会先到达链表尾部,此时快指针最多遍历整个链表一次。因此,总的时间复杂度是O(n)。

  • 空间复杂度:O(1)。我们使用了常数级别的额外空间来存储两个指针。

方式二:哈希表

思路

使用哈希表(在Python中通常使用字典)来存储已经访问过的节点。遍历链表时,对于每个节点,检查它是否已经在哈希表中。如果节点已经存在,说明链表中存在环;如果节点不存在,则将其添加到哈希表中。

代码实现

Java版本
import java.util.HashSet;
import java.util.Set;
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        while (head != null) {
            if (visited.contains(head)) {
                return true;
            }
            visited.add(head);
            head = head.next;
        }
        return false;
    }
}

说明:

  • 使用HashSet来存储访问过的节点。
  • 遍历链表,对于每个节点,检查它是否已经在HashSet中。
  • 如果在HashSet中找到了节点,则返回true表示存在环。
  • 如果遍历完整个链表都没有找到重复的节点,则返回false表示没有环。
C语言版本

在C语言中,实现哈希表会稍微复杂一些,通常可以使用数组加哈希函数来模拟哈希表的行为。但考虑到C语言标准库中没有直接支持哈希表的数据结构,这里不展示C语言的哈希表实现,而是使用其他方法(如快慢指针)来解决。

Python3版本
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        visited = set()
        while head:
            if head in visited:
                return True
            visited.add(head)
            head = head.next
        return False

说明:

  • Python中的字典(dict)可以用来作为哈希表。
  • 遍历链表,使用字典visited来存储访问过的节点。
  • 如果节点已经在visited字典中,说明链表中存在环,返回True
  • 如果遍历完整个链表都没有重复的节点,返回False

复杂度分析

  • 时间复杂度:O(n),其中n是链表的长度。我们最多需要遍历链表一次来检查每个节点。
  • 空间复杂度:O(n)。在最坏的情况下,当链表中存在环时,我们可能需要将链表中的所有节点都添加到哈希表中。因此,空间复杂度与链表的长度成正比。

总结

方式 优点 缺点 时间复杂度 空间复杂度
快慢指针 简洁高效,不需要额外空间(除了指针) 不适用于需要找到环的起始节点或环的长度的情况 O(n) O(1)
哈希表 容易理解和实现,能够检测环的存在 需要额外的空间来存储访问过的节点 O(n) O(n)

相似题目

相似题目 难度 链接
环形链表 II 中等 LeetCode 142
相交链表 中等 LeetCode 160
链表中倒数第k个节点 中等 LeetCode 19
删除链表的倒数第N个节点 中等 LeetCode 143
重新排序链表 中等 LeetCode 143
相关文章
|
26天前
|
Java
环形数组链表(java)
环形数组链表(java)
11 0
|
16天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
13 3
|
17天前
|
语音技术 Python
语音识别,python字面量,注释,变量,python变量的格式是变量名 = 变量值,加减乘除的输入方式
语音识别,python字面量,注释,变量,python变量的格式是变量名 = 变量值,加减乘除的输入方式
|
20天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
15 2
|
20天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
20天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
23天前
|
Java 编译器
Java健壮性 Java可移植性 JDK, JRE, JVM三者关系 Java的加载与执行原理 javac编译与JAVA_HOME环境变量介绍 Java中的注释与缩进 main方法的args参数
Java健壮性 Java可移植性 JDK, JRE, JVM三者关系 Java的加载与执行原理 javac编译与JAVA_HOME环境变量介绍 Java中的注释与缩进 main方法的args参数
20 1
|
7天前
|
Unix Linux Shell
Sphinx是一个Python文档生成工具,它可以解析reStructuredText或Markdown格式的源代码注释,并生成多种输出格式,如HTML、LaTeX、PDF、ePub等。
Sphinx是一个Python文档生成工具,它可以解析reStructuredText或Markdown格式的源代码注释,并生成多种输出格式,如HTML、LaTeX、PDF、ePub等。
|
1月前
|
Python
Python Google风格注释详解
Google风格注释是Python代码注释的一种标准化格式,它提供了一种规范的注释格式,使得代码更加易读、易于维护。Google风格注释使用三个双引号来包围注释内容,并按照一定规范编写。在注释中使用动词短语来描述函数的行为,并使用被动语态。在注释中使用正确的标点符号和缩进,使得注释易于阅读和理解。通过使用Google风格注释,我们可以为代码提供清晰的文档和说明,使得代码更加易读、易于维护。
34 3
|
1月前
|
Python
Python reStructuredText风格注释详解
reStructuredText风格注释是Python代码注释的一种标准化格式,它提供了一种规范的注释格式,使得代码更加易读、易于维护。reStructuredText风格注释使用两个等号来包围注释标题,并按照一定规范编写。通过使用reStructuredText风格注释,我们可以为代码提供清晰的文档和说明,使得代码更加易读、易于维护。
24 2