링크 : https://leetcode.com/problems/linked-list-cycle/

description

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.

example

Example 1:

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:

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:

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].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

풀이

코드

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head : return False
        node = head
        visitied = set()
        while node :
            if node in visitied : return True
            visitied.add(node)
            node = node.next
            
        return False

설명

쉬운 문제임에도 풀이를 쓰는 것은 새삼 자료형의 중요성을 깨달았기 때문..! 동일한 코드에서 visitied가 배열일 때와 집합 자료형일 때 런타임 속도가 꽤 큰 차이가 난다.

리스트를 쓸 때는 860ms였는데 집합 자료형으로 변경하니 52ms로 10배 이상 줄어들었다. 앞으로도 잘 생각하며 자료형을 선택하자.