LeetCode141_环形链表

2019-12-01

用python语言解答LeetCode的141题

方法一：哈希表

我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表。
常用的方法是使用哈希表

首先画一下如果链表存在环的情况，如下图所示：

avatar

如果链表存在环，那么这个链表一定从某个节点开始会出现环的入口，最后遍历经过一圈之后还会回到入口处。
题目要求检查是否存在环，那么最直接的方法是检查遍历链表的过程中是否出现某一个节点被遍历了两次。

以上面的图为例，从节点3进入后经过4,5,6,7,8后仍会回到节点3，那么这个时候节点3就被遍历了两次，那么就很容易想到第一种哈希表法。
哈希表具体实现：
我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空节点null（即已经检测到链表尾部的下一个节点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回True（即该链表为环形链表）

代码实现：


    #coding:utf-8

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

    class Solution:
        node_hash = set()
        def judge_if_in_hash(self, node):
            if node not in self.node_hash:
                self.node_hash.add(node)
                return False
            else:
                return True
        def hasCycle(self, head):
            cur = head
            while cur != None:
                flag = self.judge_if_in_hash(cur)
                if flag:
                    return True
                cur = cur.next

            return False

方法二：双指针法（快慢指针法）

解题思路：

答案有两种情况，有环无环。

分别设置快慢指针，若有环，则快慢指针必然相遇；若无环，则快指针指向NULL，返回False。

快慢指针在链表的操作中比较常见，应该作为一种常用的思路记住。还是以上面的图为例，我们设置两个指针从head开始遍历，规定两个指针的前进速度不一样，分别称为快指针、慢指针。快指针fast每次前进两个节点，慢指针slow每次前进一个节点.

avatar

因为快指针fast每次前进两个节点，一定比慢指针slow先到达环的入口处。而当慢指针slow进入环的时候，快指针fast已经经过了两个节点，如下图所示。

这个时候，我们将这个过程想象成400m跑步的追击问题。如果存在环的话，因为快指针fast速度更快，一定会追上慢指针slow。而如果快指针fast没有追上慢指针slow，则一定是因为链表不存在环。

avatar

方法二的代码实现：


    #coding:utf-8

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

    class Solution:
        def hasCycle(self, head):
            if head == None:
                return False

            slow  = fast = head

            while fast != None and fast.next != None:
                slow = slow.next
                fast = fast.next.next
                if slow == fast:
                    return True

            return False

Reference:

1.LeetCode题解–141.环形链表
https://blog.csdn.net/qq_33297776/article/details/81034628
2.leetcode环形链表_python
https://blog.csdn.net/qq_37366291/article/details/82960220