問題2.6

世界で闘うプログラミング力を鍛える150問

今回は解答みないと解けませんでした。
リスト処理でランナーテクニックって定石らしいです。
多分大学で教えてたんだろうね。ほとんど行ってなかったからね。。。

問題

循環する連結リストが与えられたとき、循環する部分の最初のノードを返すアルゴリズムを実装してください。

定義

循環を含む連結リスト：連結リストAではループを作る為に、リスト内のノードの次へのポインタが以前に出現したノードを指している。

例

入力：A -> B -> C -> D -> E -> C [最初のCと同じもの]
出力：C

importしてるpylist.pyは問題2.1で作ったものです。

http://d.hatena.ne.jp/takuto1981/20121211/1355198127

#encoding: utf-8
from pylist import Cell


def find_loop_head(head_cell):
    '''
    循環する連結リストが与えられたとき、循環する部分の最初のノードを返す関数
    >>> cell10 = Cell(10)
    >>> cell9 = Cell(9, cell10)
    >>> cell8 = Cell(8, cell9)
    >>> cell7 = Cell(7, cell8)
    >>> cell6 = Cell(6, cell7)
    >>> cell5 = Cell(5, cell6)
    >>> cell4 = Cell(4, cell5)
    >>> cell3 = Cell(3, cell4)
    >>> cell2 = Cell(2, cell3)
    >>> cell1 = Cell(1, cell2)
    >>> cell0 = Cell(0, cell1)
    >>> cell10.set_next(cell3)
    >>> find_loop_head(cell0)
    3
    >>> cell10 = Cell(10)
    >>> cell9 = Cell(9, cell10)
    >>> cell8 = Cell(8, cell9)
    >>> cell7 = Cell(7, cell8)
    >>> cell6 = Cell(6, cell7)
    >>> cell5 = Cell(5, cell6)
    >>> cell4 = Cell(4, cell5)
    >>> cell3 = Cell(3, cell4)
    >>> cell2 = Cell(2, cell3)
    >>> cell1 = Cell(1, cell2)
    >>> cell0 = Cell(0, cell1)
    >>> find_loop_head(cell0)
    '''
    # ファストランナーとスローランナーによる「ランナー」テクニック使用
    fast = head_cell
    slow = head_cell

    # ループの検出
    while True:
        # ループ無し
        if fast is None or fast.get_next() is None:
            return None
        else:
            fast = fast.get_next().get_next()
            slow = slow.get_next()
            # ループ発見
            if fast is slow:
                break

    # 先頭からループ開始点までをkとする。
    # スローランナーがループ開始点に到着した時、ファストランナーはループ開始点からkノード目。
    # ファストランナーはスローランナーより(ループサイズ - k)後方にいる。
    # ファストランナーはスローランナーに1セルずづ近づくので、(ループサイズ - k)ステップ後に衝突。
    # よってループ開始点より(ループサイズ - k)ステップ先で衝突する。つまりループ開始点までkステップの地点。
    # 以上より、衝突地点からkステップ進めたところがループ開始点。
    # 同じ速度のランナーが、リストの先頭からと、衝突点から、それぞれスタートすれば、ループ開始点で衝突する。
    fast = head_cell
    while fast is not slow:
        fast = fast.get_next()
        slow = slow.get_next()

    return fast.get_data()


def _test():
    import doctest
    doctest.testmod()


if __name__ == '__main__':
    _test()