Jianbo Dai's

lc141.环形链表

 
  • Apr 28, 2020

环形链表

因为之前做过，所以对我来说是一个简单的题（其实对谁来说都是），找链表中的环最经典的做法是用快慢指针，慢指针一次走一步，快指针一次走两步，开 始遍历后两个指针再相遇时就是环入口节点的位置。啊不过代码实现起来还是要注意一些边界，比如说要判定下一个节点是不是None，注意到快指针比较快， 应该判断快指针所指的节点的下一个节点是不是None。另外，还有一种方法是用哈希表实现，其思想是遍历链表并将每个节点的值都存在哈希表中，当某个 节点为null时，意味着已到链表末尾，所以该链表中无环，否则，当哈希表中出现重复值的时候，说明该链表中有环。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle1(self, head: ListNode) -> bool:
        if head == None or head.next == None:
            return
        slow, fast = head, head.next
        while slow != fast:
            if fast == None or fast.next == None:
                return False
            else:
                slow = slow.next
                fast = fast.next.next
        return True

    def hasCycle2(self, head: ListNode) -> bool:
        hashtable = {}
        while head != None:
            if head in hashtable:
                return True
            else:
                hashtable[head] = True
            head = head.next
        return False

follow-up：面试题：环路检测

Search