141. Linked List Cycle

水深无声 2021-12-10 08:49 224阅读 0赞

## 1. 原始题目 ##

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer `pos` which represents the position (0-indexed) in the linked list where tail connects to. If `pos` is `-1`, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.

![circularlinkedlist.png][]

Example 2:

Input: head = [1,2], pos = 0
    Output: true
    Explanation: There is a cycle in the linked list, where tail connects to the first node.

![circularlinkedlist_test2.png][]

Example 3:

Input: head = [1], pos = -1
    Output: false
    Explanation: There is no cycle in the linked list.

![circularlinkedlist_test3.png][]

## 2. 题目理解 ##

判断链表中是否有环。这个问题也是用快慢指针来解决。快指针每次走两步，慢指针每次走一步。如果存在环，那么快指针总会和慢指针在环中相遇！否则无环则快指针首先指向链表尾。关于快指针为何每次走两步，不能走3，4步的证明：[知乎][Link 1]。

## 3. 解题 ##

1 # Definition for singly-linked list.
     2 # class ListNode(object):
     3 #     def __init__(self, x):
     4 #         self.val = x
     5 #         self.next = None
     6 
     7 class Solution(object):
     8     def hasCycle(self, head):
     9         """
    10         :type head: ListNode
    11         :rtype: bool
    12         """
    13         if not head:
    14             return False
    15         cur = head
    16         pre = head
    17         if not cur.next:
    18             return False
    19         while pre:        # 因为pre总是在前面，所以判断pre即可
    20             pre = pre.next
    21             cur = cur.next
    22             if pre:       # 注意每次额外next操作时，都要先判断当前是否不为空结点
    23                 pre = pre.next
    24             if pre==cur:
    25                 return True
    26         return False

转载于:https://www.cnblogs.com/king-lps/p/10660946.html

[circularlinkedlist.png]: https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png
[circularlinkedlist_test2.png]: https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png
[circularlinkedlist_test3.png]: https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png
[Link 1]: https://zhuanlan.zhihu.com/p/60736361