C Program To Find Decimal Equivalent Of Binary Linked List

0 0 1 minute read

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<iostream>
using namespace std;
 
// Link list Node 
struct Node
{
    bool data;
    struct Node* next;
};
 
/* Returns decimal value of binary 
   linked list */
int decimalValue(struct 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)
{
    struct Node *temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}
 
// Driver code
int main()
{
    // Start with the empty list 
    struct 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;
}

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.

Please refer complete article on Decimal Equivalent of Binary Linked List for more details!

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!