Problem Explanation

Given a singly-linked list in which each node can be either 0 or 1. This linked list is a representation of a binary value, and the task is to convert this binary value to a decimal value and return it.

Consider the binary number 101 represented as an array [1, 0, 1].

• 1*2^2 = 4
• 0*2^1 = 0
• 1*2^0 = 1

When we add the above values, 4+0+1 equals 5. The decimal equivalent of 101 (base 2) is 5 (base 10).

Solution Approach

The approach to solve this problem is to traverse the linked list from left to right or from the Head node to the last node. We then convert the binary number to a decimal number on the go. To realize this, we left-shift the current decimal value by 1 (multiplying the decimal number by 2) and then add the value of the current node in the linked list.

Let's take an example to illustrate this:

We have the binary value 1011 represented in the linked list as [1, 0, 1, 1].

We start with a decimal value of 0.

• For the first node having the value 1, our decimal number becomes 1.
• The second node is 0 and our decimal now becomes 1 * 2 + 0 = 2.
• The third node is 1 and our decimal now becomes 2 * 2 + 1 = 5.
• The last node is 1 and our final decimal number becomes 5 * 2 + 1 = 11.

We return the final decimal value after traversing the entire linked list which in this example would be 11.

Solution in Python

1
2python
3class Solution:
4    def getDecimalValue(self, head):
5        
6        decimal_val = 0   # Initialize decimal value
7
8        while head:
9            decimal_val = decimal_val * 2 + head.val  # Calculation to transform binary to decimal
10            head = head.next  # Move to the next node
11
12        return decimal_val

Solution in Java

1
2Java
3public class Solution {
4    public int getDecimalValue(ListNode head) {
5
6        int decimal_val = 0;    // Initialize decimal value
7
8        while(head != null) {
9            decimal_val = decimal_val * 2 + head.val;  // Calculation to transform binary to decimal
10            head = head.next;  // Move to the next node
11        }
12
13        return decimal_val;
14    }
15}

Solution in JavaScript

1
2Javascript
3var getDecimalValue = function(head) {
4    
5    let decimal_val = 0;  // Initialize decimal value
6
7    while(head) {
8        decimal_val = decimal_val * 2 + head.val;  // Calculation to transform binary to decimal
9        head = head.next;  // Move to the next node
10    }
11
12    return decimal_val;
13};

Solution in C#

1
2C#
3public class Solution {
4    public int GetDecimalValue(ListNode head) {
5        
6        int decimal_val = 0; // Initialize decimal value
7
8        while(head != null) {
9            decimal_val = decimal_val * 2 + head.val; // Calculation to transform binary to decimal
10            head = head.next;  // Move to the next node
11        }
12
13        return decimal_val;
14    }
15}

Solution in C++

1
2C++
3class Solution {
4public:
5    int getDecimalValue(ListNode* head) {
6        
7        int decimal_val = 0;  // Initialize decimal value
8
9        while(head) {
10            decimal_val = decimal_val * 2 + head->val;  // Calculation to transform binary to decimal
11            head = head->next;  // Move to the next node
12        }
13
14        return decimal_val;
15    }
16};

In all of these examples, we create a variable decimal_val to hold the intermediate and final decimal value. We iterate through the linked list, and on each iteration, we update decimal_val to be twice its current value (which is like a left shift operation for binary numbers) plus the value of the current node. We repeat this procedure until we have processed all nodes in the linked list. Finally, we return the decimal value.# Time Complexity

The time complexity of our algorithm in all the provided solutions is O(n), where n is the number of nodes in our linked list. This is because we have to traverse all the nodes of the linked list before we can get our final decimal value.

Space Complexity

The space complexity of our algorithm is O(1), as we are only using a constant amount of extra space to store our intermediate and final decimal value which does not depend on the size of the input.

Conclusion

Converting a binary number represented as a linked list to its decimal equivalent is a fairly simple task with the right understanding of binary and decimal number systems. This task is achieved most effectively using a single pass to iterate through the linked list, performing binomial calculations at each node until the end of the list is reached. We provided code implementations in Python, Java, JavaScript, C# and C++ which show how this can be done effectively. We also analysed the time and space complexities of our approach, which revealed it to be an efficient solution in terms of computational resources used.