問題2.4

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

昨日呑みに行ったばかりに、せっかく毎日書いてたブログが早速途切れてしまった。
ってか今日も明日も明々後日も呑みなんだけど。師走。。。

問題

ある数xが与えられたとき、連結リストの要素を並べ替え、xより小さいものが前にくるようにするコードを書いてください。

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 dimidiate_list(linked_list, number):
    '''
    numberより小さい値と、number以上の値とで、linked_listを二分する関数
    >>> linked_list = LinkedList()
    >>> linked_list.insert(0, 100)
    >>> linked_list.insert(1, 200)
    >>> linked_list.insert(2, 300)
    >>> linked_list.insert(3, 250)
    >>> linked_list.insert(4, 150)
    >>> linked_list.insert(5, 500)
    >>> dimidiate_list(linked_list, 300)
    >>> linked_list.index(100)
    0
    >>> linked_list.index(200)
    1
    >>> linked_list.index(250)
    2
    >>> linked_list.index(150)
    3
    >>> linked_list.index(300)
    4
    >>> linked_list.index(500)
    5
    '''
    # numberより小さい値リストの先頭と末尾セル
    smaller_linked_list_head = None
    smaller_linked_list_tail = None
    # number以上リストの先頭と末尾セル
    bigger_linked_list_head = None
    bigger_linked_list_tail = None

    # numberより小さい値とnumber以上の値とでリスト分割
    cell = linked_list.get_top()
    while cell:
        if cell.get_data() < number:
            if not smaller_linked_list_head:
                smaller_linked_list_head = cell
                smaller_linked_list_tail = cell
            else:
                smaller_linked_list_tail.set_next(cell)
                smaller_linked_list_tail = cell
        else:
            if not bigger_linked_list_head:
                bigger_linked_list_head = cell
                bigger_linked_list_tail = cell
            else:
                bigger_linked_list_tail.set_next(cell)
                bigger_linked_list_tail = cell
        cell = cell.get_next()

    # 2つのリストを連結
    smaller_linked_list_tail.set_next(bigger_linked_list_head)


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


if __name__ == '__main__':
    _test()

備考

テキストだと別の解き方も紹介してます。説明するのは面倒なので省略するけど、リストの並びが変わっちゃ駄目とは書いてないから、その方法もたしかに・・・って感じ。