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