LeetCode-141 环形链表 --- Python代码实现及详解

朱雀 2020-10-31 18:29 536阅读 0赞

### 题目： ###

给定一个链表，判断链表中是否有环。

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

示例 1：

输入：head = [3,2,0,-4], pos = 1
    输出：true
    解释：链表中有一个环，其尾部连接到第二个节点。

![2019100723485075.png][]

示例 2：

输入：head = [1,2], pos = 0
    输出：true
    解释：链表中有一个环，其尾部连接到第一个节点。

![20191007234858659.png][]

示例 3：

输入：head = [1], pos = -1
    输出：false
    解释：链表中没有环。

![20191007234911102.png][]

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

### 思路： ###

使用哈希法思想。**循环遍历每个节点，把遍历过的节点val值置为空，只要遍历过程中有head.next为空则说明不是环形的，否则遍历完每个节点没有head.next为空说明是环形的。**

### 编码实现： ###

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def hasCycle(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            if not head:
                return False
            while head.next and head.val != None:
                head.val = None  # 遍历的过程中将值置空
                head = head.next
            if not head.next:  # 如果碰到空发现已经结束，则无环
                return False
            return True  # 否则有环

[2019100723485075.png]: /images/1604168957200.png
[20191007234858659.png]: /images/1604168936026.png
[20191007234911102.png]: /images/1604168915286.png