Given a Singly Linked List containing n nodes, each node of the list can hold either 0 or 1 and the most significant bit is present at the head of the linked list. The entire linked list is a binary representation of a decimal number. Return the decimal value represented by the given binary linked list.
Note: The linked list is not empty and the maximum number of nodes will be less than 30.
Example 1: Input: 1->0->1->1 Output: 11 Example 2: Input: 1->0->1 Output: 5
Approach 1: Converting Binary Using Arithmetic calculation.
You can solve this problem by diving the problem into two sub-problems:
- Find the number of binary digits present in the given linked list that is needed for the arithmetic calculation.
- Convert the Binary to a Decimal number using classic arithmetic calculation (see the above image).
C++ Solution Code:
//C++ Program to convert Binary Linked List to Decimal #include<bits/stdc++.h> using namespace std; class ListNode{ public: int data; ListNode *next; //constructor ListNode(int data){ this->data = data; this->next = NULL; } }; //creating new node ListNode *newNode(int data){ ListNode *temp = new ListNode(data); temp->next = NULL; return temp; } //function to find length of linked list int listLength(ListNode* head){ ListNode *temp = head; int len = 0; while(temp != NULL){ temp = temp->next; len++; } return len; } //function to convert binary to decimal int getDecimalValue(ListNode *head){ int len = listLength(head); int ans = 0; ListNode *temp = head; int i = 1; while(temp != NULL){ int res = (temp->data)*pow(2, len-i); temp = temp->next; i++; ans += res; } return ans; } int main(){ ListNode *head = newNode(1); head->next = newNode(0); head->next->next = newNode(1); cout<<"Integer Value: "<<getDecimalValue(head); return 0; }
Integer Value: 5
- Time Complexity: O(n)
- Space Complexity: O(1)
In this approach, bit manipulation technique in which we will traverse the linked list starting from head till end. Updating the current value with head->next->value. Updating the result by shifting the digit by one to the left and performing logical OR with current vlaue.
C++ Solution code:
/*C++ Program to convert Binary Linked List to Decimal Using bit manipulation*/ #include<bits/stdc++.h> using namespace std; class ListNode{ public: int data; ListNode *next; //constructor ListNode(int data){ this->data = data; this->next = NULL; } }; //creating new node ListNode *newNode(int data){ ListNode *temp = new ListNode(data); temp->next = NULL; return temp; } //function to convert binary to decimal int getDecimalValue(ListNode *head){ int num = head->data; while (head->next != NULL) { num = (num << 1) | head->next->data; head = head->next; } return num; } int main(){ ListNode *head = newNode(1); head->next = newNode(0); head->next->next = newNode(1); cout<<"Integer Value: "<<getDecimalValue(head); return 0; }
Integer Value: 5
- Time Complexity: O(n)
- Space Complexity: O(1)
Related Articles:
