C++ Program To Find Decimal Equivalent Of Binary Linked List
Given a singly linked list of 0s and 1s find its decimal equivalent.
Input: 0->0->0->1->1->0->0->1->0 Output: 50 Input: 1->0->0 Output: 4
The decimal value of an empty linked list is considered as 0.
Initialize the result as 0. Traverse the linked list and for each node, multiply the result by 2 and add the node’s data to it.
C++
// C++ Program to find decimal value // of binary linked list #include <bits/stdc++.h> using namespace std; // Link list Node class Node { public : bool data; Node* next; }; /* Returns decimal value of binary linked list */ int decimalValue(Node *head) { // Initialized result int res = 0; // Traverse linked list while (head != NULL) { // Multiply result by 2 and // add head's data res = (res << 1) + head->data; // Move next head = head->next; } return res; } // Utility function to create a // new node. Node *newNode( bool data) { Node *temp = new Node; temp->data = data; temp->next = NULL; return temp; } // Driver code int main() { // Start with the empty list Node* head = newNode(1); head->next = newNode(0); head->next->next = newNode(1); head->next->next->next = newNode(1); cout << "Decimal value is " << decimalValue(head); return 0; } // This is code is contributed by rathbhupendra |
Output :
Decimal value is 11
Time Complexity: O(n) where n is the number of nodes in the given linked list.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Another Approach(by reversing the Linked List):
Follow the below steps to solve the given problem
1) First reverse the given linked list.
2) Initialize a ans variable to store ans and pos variable to keep track of position of node in linked list.
3) Perform the operation ans = ans + (rhead.data*(2**pos))%MOD)
4) perform ans = ans%MOD
Below is the implementation of above approach:
C++
#include<bits/stdc++.h> using namespace std; // C++ Program to find decimal value // of binary linked list // node structure struct Node{ int data; Node* next; Node( int data){ this ->data = data; this ->next = NULL; } }; long long unsigned int power( int num, int count){ if (count ==0) return 1; if (count%2==0) return (power(num,count/2)%1000000007)*(power(num,count/2)%1000000007); else return num*(power(num,count/2)%1000000007)*(power(num,count/2)%1000000007);; } Node* reverse(Node* head){ if (head == NULL || head->next == NULL) return head; Node* curr = head; Node* prev = NULL; Node* nxt = head->next; while (nxt != NULL){ curr->next = prev; prev = curr; curr = nxt; nxt = nxt->next; } curr->next = prev; return curr; } int decimalValue(Node* head){ int MOD = 1000000007; Node* rhead = reverse(head); int ans = 0; int pos = 0; while (rhead != NULL){ ans = (ans%MOD + ((rhead->data)*power(2,pos)) % MOD) % MOD; rhead = rhead->next; pos++; } return ans; } int main(){ Node* head = new Node(1); head->next = new Node(0); head->next->next = new Node(1); head->next->next->next = new Node(1); cout<< "Decimal Value is : " <<decimalValue(head); } |
Decimal Value is : 11
Time Complexity: O(N) where N is the number of nodes in linked list.
Auxiliary Space: O(1)
Please refer complete article on Decimal Equivalent of Binary Linked List for more details!