LeetCode / Linked List Cycle II

（ブログ記事からの転載）

[https://leetcode.com/problems/linked-list-cycle-ii]

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)が含まれている場合、cycleが始まる地点を返す必要があります。
そしてこの問題でも、空間計算量を定数時間に抑えて行う方法を考えます。

解答・解説

解法1

空間計算量を定数時間に抑えるということで、ポインタを使うんだなということは想像がつきます。実際、今回も1ずつ進むslowと2ずつ進むfastのポインタを使います。しかし今回はcycleが始まる地点も返す必要があり、これをどうメモリを使わずに計算するかです。

これはなかなか自力で思いつきづらい気がしますが、下図のような状況を考えます。

slowとfastを同じ地点からスタートさせ（前の問題ではスタート地点を1ずらしていました）、次にslowとfastが出会うまでの間に、slowがH+D進み、fastはH+L+D進む状況を考えます。
すると、fastはslowの2倍の距離進んでいるので、2(H + D) = H + D + L の関係が成り立ちます。移項すれば、H = L - D の関係が成り立ちます。

求めたいcycleが始まる地点は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