Chuyển số nhị phân trong danh sách liên kết sang số nguyên trong C++

Cho head tham chiếu đến danh sách liên kết đơn. Mỗi nút giá trị 0 hoặc 1. Danh sách lưu biểu diễn nhị phân của một số. Trả về giá trị thập phân. Ví dụ: [1,0,1,1,0,1] → 45.

Giải pháp:

• Chuyển danh sách thành mảng.
• Đảo ngược mảng.
• ans := 0, temp := 1.
• Duyệt mảng: ans += x[i] * temp; temp *= 2.
• Trả về ans.

Ví dụ 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, temp = 1;
        for (int i = 0; i < x.size(); i++) {
            ans += x[i] * temp;
            temp *= 2;
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,0,1,1,0,1};
    ListNode *head = make_list(v);
    cout << ob.getDecimalValue(head);
}

Đầu vào

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

Đầu ra

45