LeetCode: 141. Linked List Cycle

题目

原题地址：https://leetcode.com/problems/linked-list-cycle/

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Example 1:

image1

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

Example 2:

image2

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

Example 3:

image3

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

Constraints:

  • The number of the nodes in the list is in the range [0, 104].
  • -10^5 <= Node.val <= 10^5
  • pos is -1 or a valid index in the linked-list.

解法

遍历链表，记录访问过的节点，判断是否存在环

遍历链表，把访问过的节点都记下来，如果发现有节点指向了一个已访问过的节点，说明链表存在环。

这个方法的 Python 代码类似下面这样:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head):
        if head is None:
            return False
        seen = {}
        while head is not None:
            if head in seen:
                return True

            seen[head] = True
            head = head.next

        return False

快慢双指针方法，检查是否会相遇

快慢双指针的方法的思路是：

  • 定义快和慢两个指针，从 head 开始遍历链表，慢指针一次移动一个节点，快指针一次移动两个节点
  • 如果快指针到达了链表尾部，说明没有环（因为如果有环的话，会死循环没有尾部）
  • 如果快指针和慢指针移动到了同一个节点上，说明有环（因为如果没环的话，快指针永远在慢指针前面，有环时，因为快指针比慢指针移动的速度要快，在移动到有环的地方的时候会跑到慢指针后面去（多次移动后会出现），最终出现快慢两个指针相遇移动到同一个节点的情况（多次移动后出现））

这个方法的 Python 代码类似下面这样:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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

        slow, fast = head, head

        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next

            if fast is slow:
                return True

        return False

Comments