C++で連結リストの2進数を10進数の整数に変換する方法

問題概要

片方向連結リストの先頭ノードへの参照 head が与えられるとします。連結リストの各ノードには 0 または 1 の値が格納されており、この連結リストはある数値の2進表現を保持しています。求めたいのは、連結リストが表す数値を10進数に変換した値です。

例えば、リストが [1,0,1,1,0,1] の場合、2進数「101101」は10進数では 45 に相当するため、答えは 45 となります。

解法の考え方

この問題は、以下の手順で解くことができます。

• 連結リストの要素を配列(ベクター)に変換する
• その配列を逆順に並べ替える
• ans = 0、temp = 1 として初期化する
• i を 0 から配列サイズ − 1 までループ処理する
  • ans = ans + x[i] * temp
  • temp = temp * 2
• ans を返す

リストを逆順にすることで、最下位ビットから順に処理できるのがポイントです。各桁の値に 1、2、4、8… と2倍されていく重みを掛けながら加算していくことで、2進数から10進数への変換が実現できます。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class ListNode{
    public:
        int val;
        ListNode *next;
        ListNode(int data){
            val = data;
            next = NULL;
        }
};
ListNode *make_list(vector<int> v){
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        ListNode *ptr = head;
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return head;
}
class Solution {
public:
    vector <int> getVector(ListNode* node){
        vector <int> result;
        while(node){
            result.push_back(node->val);
            node = node->next;
        }
        return result;
    }
    int getDecimalValue(ListNode* head) {
        vector <int> x = getVector(head);
        reverse(x.begin(), x.end());
        int ans = 0;
        int temp = 1;
        for(int i = 0; i < x.size(); i++){
            ans += x[i] * temp;
            temp *= 2;
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,0,1,1,0,1};
    ListNode *head = make_list(v);
    cout << ob.getDecimalValue(head);
}

入力

[1,0,1,1,0,1]

出力

45