141. Linked List Cycle

题目描述和难度

• 题目描述：

• 题目难度：简单。
• 英文网址：141. Linked List Cycle 。
• 中文网址：141. 环形链表 。

思路分析

求解关键：

参考解答

参考解答1：使用 Hash 表判断是否重复（不推荐）。

# 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 head is None:
            return False
        hash_tabel = dict()
        point = head
        while point:
            if point in hash_tabel:
                return True
            else:
                hash_tabel[point] = 0
            point = point.next
        return False

参考解答2：设置快慢指针的方式。

# 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 head is None:
            return False
        slow = head
        fast = head
        # 快指针每走一步，都做了判断
        while fast:
            fast = fast.next

            if fast:
                fast = fast.next
                slow = slow.next
            else:
                return False
            if fast == slow:
                return True
        return False

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0141-linked-list-cycle ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。