Convert Binary Linked List to Integer.

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

Output:

Integer Value: 5

Time Complexity: O(n)
Space Complexity: O(1)

Approach 2: Using Bit Manipulation.

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

Output:

Integer Value: 5

Time Complexity: O(n)
Space Complexity: O(1)

Related Articles:

Find the Middle of the Singly Linked List in C++.

Reverse a Singly Linked List in C++.

Merge Two Sorted Linked List in C++.

Intersection Point of Two Linked Lists in C++.

Detect Cycle in a Linked List in C++.

Convert Binary Linked List to Integer.

No comments:

Post a Comment