（ブログ記事からの転載）
[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