Pythonで2進数を表すリンクリストを10進数に変換する方法

問題の概要

片方向リンクリスト(単方向連結リスト)があり、このリンクリストは最上位桁(MSB)から順に並んだ2進数を表しているとします。このリンクリストを受け取り、対応する10進数の値を返すプログラムを作成しましょう。

たとえば、入力が [1,0,1,1,0] の場合、2進数「10110」は10進数で 22 になるため、出力は 22 となります。

解決の手順

以下のステップで処理を進めます。

• 空のリスト l を用意する
• ノードが null になるまで、各ノードの値を l の末尾に追加し、node を次のノードへ進める
• k := 0、v := 0 と初期化する
• i をリストの末尾(サイズ − 1)から先頭(0)まで逆順に走査しながら、次を繰り返す
  • l[i] が 1 ならば、v に 2^k を加算する
  • k を 1 増やす
• 最後に v を返す

Pythonでの実装例

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

class Solution:
    def solve(self, node):
        l = []
        while node:
            l.append(node.val)
            node = node.next
        k = 0
        v = 0
        for i in range(len(l) - 1, -1, -1):
            if l[i] == 1:
                v += (2 ** k)
            k += 1
        return v

ob = Solution()
head = make_list([1, 0, 1, 1, 0])
print(ob.solve(head))

入力

[1,0,1,1,0]

出力

22

より効率的な方法:ビットシフトを活用

上記の方法では、一度すべての値をリストに格納してから計算しています。しかし、リンクリストを先頭から走査しながら「v = v × 2 + 現在の桁の値」と更新していけば、追加のリストが不要になり、1回の走査(O(n))で変換できます。

class Solution:
    def solve(self, node):
        v = 0
        while node:
            v = v * 2 + node.val
            node = node.next
        return v

この操作は左シフト(v << 1 | node.val)と同等であり、時間計算量は O(n)、空間計算量は O(1) となるため、メモリの面でも有利です。

まとめ

2進数を表すリンクリストを10進数に変換するには、各桁の位置に応じて 2 のべき乗を加算する方法が基本です。リスト経由の方法は理解しやすく、ビット演算を直接使う方法は効率に優れています。用途に応じて使い分けるとよいでしょう。