如何判断单链表有无环

判断一个单链表是否存在环，也称为环形链表，可以使用两个指针法，通常称为快慢指针或者龟兔赛跑算法。以下是步骤：

1. **初始化两个指针**：首先创建两个指针，一个指向链表的头节点（快指针），另一个也指向头节点（慢指针）。

2. **移动指针**：快速指针每次向前跳两步，而慢速指针每次只走一步。如果链表不存在环，则最终快指针会到达链表的末尾，此时慢指针还在原地；如果有环，快指针会在某个点追上慢指针。

3. **检查环**：当快慢指针相遇时，说明链表存在环。为了确定环的入口，将其中一个指针恢复到头节点，然后同时让两个指针再次从相遇点开始移动，当它们再次相遇时，相遇的位置就是环的入口。

4. **结论**：如果没有找到环（即快指针达到末尾），那么链表就没有环。如果有环，返回环的入口。

相关问题

判断单链表有环

要判断单链表是否有环，可以使用双指针法，即快慢指针法。具体实现如下：

定义两个指针 slow 和 fast，初始时都指向链表的头节点。
slow 指针每次向后移动一个节点，fast 指针每次向后移动两个节点。
如果链表有环，那么 fast 指针一定会追上 slow 指针，此时可以判断链表有环；如果链表没有环，那么 fast 指针会先到达链表的末尾，此时可以判断链表没有环。
以下是具体的实现代码：

def has_cycle(head):
    if not head or not head.next:
        return False
    
    slow = head
    fast = head.next
    
    while fast and fast.next:
        if slow == fast:
            return True
        slow = slow.next
        fast = fast.next.next
    
    return False

其中，head 为链表的头节点，函数返回 True 表示链表有环，返回 False 表示链表没有环。

判断单链表是否有环

判断单链表是否有环可以使用快慢指针的方法。

定义两个指针，一个快指针和一个慢指针，初始时均指向链表头部。快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，则快指针最终会追上慢指针，此时链表有环；如果链表不存在环，则快指针会先到达链表尾部，此时链表无环。

以下是该算法的示例代码：

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

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

其中，`ListNode` 是单链表节点的定义，`hasCycle` 是判断单链表是否有环的函数。函数中，如果链表为空或只有一个节点，直接返回 False。然后，定义快慢指针，慢指针指向头节点，快指针指向头节点的下一个节点。当快指针追上慢指针时，说明链表有环，返回 True；当快指针到达链表尾部时，说明链表无环，返回 False。