問題2.2

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

夕飯休憩中にもう1問。
テキストだと再帰で解いてますね。
まぁなんとなく分かるけど、再帰って頭こんがらがるんですよね。。。
ってことで地味な方法でやります。

問題

単方向連結リストにおいて、末尾から数えてk番目の要素を見つけるアルゴリズムを実装してください。

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

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

#encoding: utf-8
from pylist import Cell
from pylist import LinkedList


def index_from_last(linked_list, offset_from_last):
    '''
    単方向リスト中で、末尾から数えてoffset_from_last番目の要素を取得する関数
    # リストの先頭セル取得
    >>> linked_list = LinkedList()
    >>> linked_list.insert(0, 'a')
    >>> linked_list.insert(1, 'b')
    >>> linked_list.insert(2, 'c')
    >>> linked_list.insert(3, 'd')
    >>> linked_list.insert(4, 'e')
    >>> linked_list.insert(5, 'f')
    >>> index_from_last(linked_list, 2)
    'e'
    '''
    cell = linked_list.get_top()

    # リストの長さ取得
    list_length = 1
    while cell.get_next():
        list_length += 1
        cell = cell.get_next()

    # 指定セルの取得
    cell = linked_list.get_top()
    offset = list_length - offset_from_last
    for counter in range(0, offset):
       cell = cell.get_next()

    return cell.get_data()


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


if __name__ == '__main__':
    _test()