• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【leetcode】141:环形链表

开发技术 开发技术 1周前 (04-08) 4次浏览

 

【leetcode】141:环形链表

 【leetcode】141:环形链表

 

 

 这题一看实在是太简单了,只要判断我们当前指针所在的元素是否已经被访问过就好。因此有第一种方法:

方法一:

使用数组储存我们访问过的所有元素,然后遍历我们访问过的所有元素和当前指针所在的元素进行比较,如果有地址一样的,就返回True说明是环形链表,不然就返回False,说明不是环形链表。时间复杂度为O(n^2)

代码如下:

# 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:
        node_list=[]
        while head!=None:
            if head in node_list:
                return True
            node_list.append(head)
            head=head.next

        return False

方法二:

弃用数组,改用哈希表来储存数据,查找的时间复杂度立刻降低为了O(1),总体的时间复杂度为O(n)。

# 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:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

方法三:

使用快慢指针,如果有环形链表,那么快慢指针总会相遇,如果在相遇之前就已经走到了底,说明不是环形链表,时间复杂度为O(n),但是由于快慢指针可能要走2n个step,不用大O表示法的话,实际上会比哈希表稍微慢一些,代码如下:

# 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:
        #使用哈希表确实能够节省不少时间
        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

 


程序员灯塔
转载请注明原文链接:【leetcode】141:环形链表
喜欢 (0)