LeetCode. Linked List Cycle [Linked List]

Problem:

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.

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.

Example 3:

Input: head = [1], pos = -1

Output: false

Explanation: There is no cycle in the linked list.

-Summary-

Using Tortoise and Hare algorithm

1. keep move slow(move1) and fast(move2) until both are meet

2. if slow or fast can't move anymore, which means it does not have a cycle.

오늘도 새로운 알고리즘과 푸는 방법들을 새로 배운다.

leetcode.com/problems/linked-list-cycle/discuss/44607/In-place-Python-code-beats-90

def hasCycle(self, head):
    fast = slow = head

    while slow and fast and fast.next:
        slow = slow.next                # Step of 1
        fast = fast.next.next           # Setp of 2

        if slow is fast:                # Checking whether two pointers meet
            return True

    return False

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]