LeetCode 141. 环形链表-猿码集

LeetCode 141. 环形链表

LeetCode是一个非常受欢迎的在线编程平台，通过解决算法和数据结构问题来提高编程能力。其中，141. 环形链表是一道常见的链表问题。本文将解释这个问题的要求，并给出解决方案。

问题描述

给定一个链表，判断链表是否有环。如果链表中有一个节点，使得从该节点出发，可以沿着链表的下一个指针再次到达该节点，则链表中存在环。例如，下面的链表就是一个环形链表：


  3 -> 2 -> 0 -> -4
       |         |
       -----------

应返回True，因为通过下一个指针依次遍历，可以回到起始节点2。

如果链表中没有环，则返回False。例如，以下链表不是环形链表：


1 -> 2 -> 3 -> 4

应返回False，因为没有节点可以回到起始节点1。

解决方案

要判断链表是否有环，可以使用快慢指针的方法。我们使用两个指针，一个指针每次向后移动一步，另一个指针每次向后移动两步。如果链表中存在环，那么快指针最终会追上慢指针，并且两个指针会指向同一个节点。如果链表中没有环，那么快指针最终会到达链表的末尾，即指向空节点。

算法实现

根据上述思路，我们可以使用Python来实现该算法。首先，我们定义一个辅助函数，用于创建链表节点：


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

然后，我们定义一个函数来判断链表是否有环：


def hasCycle(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

接下来，我们可以使用上述代码来判断链表是否有环。


# 创建链表
node1 = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2
# 判断链表是否有环
result = hasCycle(node1)
print(result)  # True

上述代码中，我们创建了一个环形链表，并使用hasCycle函数判断是否有环。最后，输出结果为True。

时间复杂度分析

该算法使用了快慢指针，两个指针的移动速度不同。当链表中存在环时，快指针会追上慢指针，因此时间复杂度为O(n)。当链表中不存在环时，快指针会到达链表的末尾，因此时间复杂度也为O(n)。因此，总的时间复杂度为O(n)。

空间复杂度分析

该算法只使用了常数级别的额外空间，因此空间复杂度为O(1)。

总结

本文介绍了LeetCode 141. 环形链表问题的解决方案。通过使用快慢指针算法，我们可以高效地判断链表是否有环。该算法的时间复杂度为O(n)，空间复杂度为O(1)。在解决类似问题时，我们可以运用这个思路，提高算法的效率。

LeetCode 141. 环形链表