Leetcode题141、环状链表(Python题解)腾讯面试题

Source

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

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

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?
在这里插入图片描述

题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/linked-list-cycle

难度:简单

分析
有两种方法可以用于判断环状指针,一种是快慢指针,如果快指针可以追上慢指针,那么即成环。一种是用哈希表存储结点,当结点开始重复时,即成环。

解决方法
1:快慢指针

#方法一、快慢指针
#超过75%
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = fast = head
        while fast and fast.next:
            if slow == fast:
                return True
            slow = slow.next
            fast = fast.next.next
        return False

复杂度:O(n)

2:哈希

#方法二、哈希
#超过58%
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        hashMap = {
    
      }
        while head:
            if hashMap.get(head) is not None:
                return True
            hashMap[head] = 1
            head = head.next
        return False

复杂度:O(n)