Chuyển đổi số nhị phân trong danh sách được liên kết thành số nguyên trong C ++

Giả sử chúng ta có một "head" là một nút tham chiếu đến một danh sách được liên kết đơn lẻ. Giá trị của mỗi nút có trong danh sách liên kết là 0 hoặc 1. Danh sách liên kết này lưu trữ biểu diễn nhị phân của một số. Chúng ta phải trả về giá trị thập phân của số có trong danh sách liên kết. Vì vậy, nếu danh sách như [1,0,1,1,0,1]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• x:=chuyển đổi các phần tử danh sách thành một mảng

• sau đó đảo ngược danh sách x

• ans:=0 và temp:=1

• cho tôi trong phạm vi i:=0, với kích thước x - 1

  • ans:=ans + x [i] * temp

  • temp:=temp * 2

• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

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

Đầu ra

45