LeetCode/Linked List Cycle

( 블로그 기사 의 전재)

Kaggle 연결로 트위터에서 팔로우하거나 팔로우한 사람이 혹은 옛 지의 바둑 친구였던 건.
방금 오늘 문제의 링크리스트와 같이 돌아서 재회했습니다 (무리 야리

[ h tps : // / ㅇ t 여기. 코 m / p 로b ㎇ ms / 펜케 d ぃ st cyc ぇ / ]

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.


연결 목록이라는 데이터 구조가 주제입니다.
주어진 연결 리스트에 순환 구조가 포함되어 있는지(=순환 리스트), 판정하는 문제입니다.

해답·해설

해법 1

처음으로 연결 리스트라는 데이터 구조를 본 사람이 기존의 지식으로 대응하려고 하면 다음과 같이 된다고 생각합니다.

# 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):
        nodesSeen = set()
        while head is not None:
            if head in nodesSeen:
                return True
            else:
                nodesSeen.add(head)
            head = head.next
        return False

각 요소를 set에 점점 넣어 가서 이미 set에 들어있는 요소를 다시 만나면 순환하고 있다는 것이므로 True를 반환하고 그런 일이 일어나지 않고 더 이상 요소가 없는 곳까지 루프가 돌 일단 False를 반환하면 됩니다.

해법 2

해법 1에서는 공간 계산량은 $O(n)$가 됩니다만, 이것을 정수 시간으로 실시하는 방법이 이하의 코드입니다.

slow와 first라는 두 개의 포인터를 준비합니다. slow는 1요소씩, first는 2요소씩 진행하는 포인터로, slow의 1개 앞에 first를 두고 스타트 시킵니다.
그러면 순환리스트라면, slow가 리스트의 종단까지 진행되는 동안, first는 반드시 어딘가에서 slow를 만나게 됩니다.

왜냐하면, slow가 리스트의 종단까지 진행하는 n스텝의 사이에 first는 2n 전진하게 됩니다만, first가 따라잡아야 하는 slow와의 거리는, 최대로 아래 그림의 경우에서 2n-1이므로, 1요소씩 거리를 채우는 first는 n단계 동안 반드시 slow로 따라잡을 것입니다.

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False
        slow = head
        fast = head.next
        i = 0
        while slow is not fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True