141. Linked List Cycle

题目描述和难度

  • 题目描述:

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

进阶:
你能否不使用额外空间解决此题?

思路分析

求解关键:

参考解答

参考解答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