問題2.7

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

問題集だと、また再帰で解いてますね。
再帰ねー。数学脳じゃないんで、どうも苦手。
はやくこの問題集終わらせて、オライリーの「デバッグの理論と実装」読みたいので、再帰はやりませぬ。
って、まだ問題集130問以上あるけどね。。。

問題

連結リストが回文(先頭から巡回しても末尾から巡回しても、各ノードの要素がまったく同じになっている)かどうかを調べる関数を実装してください。

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 is_kaibun(linked_list):
    '''
    連結リストが示す文が回文かどうかをチェックする関数
    >>> linked_list = LinkedList()
    >>> linked_list.insert(0, 'a')
    >>> linked_list.insert(1, 'b')
    >>> linked_list.insert(2, 'c')
    >>> linked_list.insert(3, 'b')
    >>> linked_list.insert(4, 'a')
    >>> is_kaibun(linked_list)
    True
    >>> linked_list2 = LinkedList()
    >>> linked_list2.insert(0, 'a')
    >>> linked_list2.insert(1, 'b')
    >>> linked_list2.insert(2, 'c')
    >>> linked_list2.insert(3, 'b')
    >>> linked_list2.insert(4, 'b')
    >>> is_kaibun(linked_list2)
    False
    '''
    # 「ランナー」テクニック使用
    fast = linked_list.get_top()
    slow = linked_list.get_top()

    # リストの前半を入れるスタック
    stack_list = []

    # リストの真ん中を調べる
    while True:
        if not fast.get_next() or not fast.get_next().get_next():
            list_target = slow.get_next()
            break
        else:
            # リストの前半はスタックに入れる
            stack_list.append(slow.get_data())
            fast = fast.get_next().get_next()
            slow = slow.get_next()

    # リストの前半と後半を比較
    while len(stack_list) > 0:
        if stack_list.pop() != list_target.get_data():
            return False
        list_target = list_target.get_next()

    return True


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


if __name__ == '__main__':
    _test()