LeetCode/Linked List Cycle II

( 블로그 기사 의 전재)

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

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

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.

Note: Do not modify the linked list.

Follow-up:
Can you solve it without using extra space?

이 문제 다음에 연결 목록이 주제.
이 문제는 주어진 연결 목록에 순환 구조 (cycle)가 포함되어 있으면 사이클이 시작되는 지점을 반환해야합니다.
그리고 이 문제에서도, 공간 계산량을 정수 시간으로 억제해 실시하는 방법을 생각합니다.

해답·해설

해법 1

공간 계산량을 정수 시간으로 억제한다고 하는 것으로, 포인터를 사용하지 말라는 것은 상상이 붙습니다. 실제로 이번에도 1씩 진행하는 slow와 2씩 진행하는 fast 포인터를 사용합니다. 그러나 이번에는 사이클이 시작되는 지점도 반환해야 하며, 이것을 어떻게 메모리를 사용하지 않고 계산하는지입니다.

이것은 좀처럼 자력으로 생각하기 어려운 생각이 듭니다만, 아래 그림과 같은 상황을 생각합니다.

slow와 fast를 같은 지점에서 스타트시키고(전의 문제에서는 스타트 지점을 1 시프트하고 있었습니다), 다음에 slow와 fast가 만날 때까지의 사이, slow가 H+D 진행해, fast는 H+L+D 진행 상황을 생각합니다.
그러면, fast는 slow의 2배의 거리 진행하고 있으므로, 2(H + D) = H + D + L 의 관계가 성립합니다. 이항하면 H = L - D 관계가 성립합니다.

요구하고 싶은 사이클이 시작되는 지점은 H에 상당합니다만, H = L - D 라고 하는 것은, 아래 그림과 같이 slow를 fast와 만난 지점에서 스타트시키고, 한편으로 head라고 하는 포인터를 시작점으로부터 스타트시켰을 때 , 그냥 cycle의 시작점에서 만나는 것을 의미합니다.

즉, 우선 slow와 fast를 같은 지점에서 스타트시키고, slow와 fast가 만나면, 거기에서 slow만 스타트시키고, 동시에 시점에서 head를 스타트시키면, slow와 head가 만난 지점이 요구하고 싶은 대답이다 라는 것입니다.

코드에 떨어뜨리면 다음과 같습니다.

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = fast = head
        # まず、slowとfastが再び出会うまで動かす
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                break
        else:
            return None
        # slowとheadが出会うまで動かす
        while head is not slow:
            slow = slow.next
            head = head.next
            print(head.val, slow.val)
        return head