Problem Statement

Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.

Return the decimal value of the number in the linked list.

The most significant bit is at the head of the linked list.

Examples

Example 1:

Input: head = [1, 0, 1]
Output: 5

Explanation: (101) in base 2 = (5) in base 10 (decimal)

Example 2:

Input: head = [0]
Output: 0

Explanation: 0 is same in both decimal and binary.

Different Approaches

1️⃣ Brute Force Approach

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        // Temporary pointer to traverse the linked list
        ListNode* current = head;

        // Vector to store binary digits from the linked list
        vector<int> binaryDigits;
        while (current != nullptr) {
            binaryDigits.push_back(current->val);
            current = current->next;
        }

        // Variable to store the final decimal number
        int decimalValue = 0;

        // Power tracker to calculate 2^power for each bit
        int power = 0;

        // Process the binary digits in reverse order (from LSB to MSB)
        while (!binaryDigits.empty()) {
            int lastBit = binaryDigits.back();  // Get the last bit
            binaryDigits.pop_back();           // Remove the last bit

            // Calculate 2^power using repeated multiplication
            int exponent = 1;
            int powerCounter = 0;
            while (powerCounter != power) {
                exponent *= 2;
                powerCounter++;
            }
            power++;

            // Add the contribution of the current bit to the decimal value
            decimalValue += lastBit * exponent; 
        }

        return decimalValue;
    }
};

Complexity Analysis:

• Time Complexity: O(n^2)
  • O(n): For traversing the list to populate binary digits to an vector.
  • O(n^2): The inner while loop computes 2^power, requiring O(power) multiplications in the worst case.
    • As power increments linearly, the total cost across all iterations becomes:
      • O(1 + 2 + 3 + .. + n) = O(n^2)
  • Overall Time Complexity: O(n) + O(n^2) = O(n^2)
• Space Complexity: O(n)
  • As we use vector to store the binary digits.

2️⃣ Optimal Approach

Intuition:

Instead of storing binary digits, directly compute the decimal value during the traversal using bit manipulation or multiplication.

Key Observation: The binary number can be constructed as you traverse by shifting the accumulated result left by 1 bit (equivalent to multiplying by 2) and adding the current node's value.

Steps:

1. Initialize a result variable to 0.
2. Traverse the linked list and update the result as:
   1. result = (result * 2) + current node's value
3. Return the result.

Code:

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int getDecimalValue(ListNode* head) {
    int result = 0;

    while (head) {
        result = (result << 1) | head->val; // Shift left and add current value
        head = head->next;
    }

    return result;
}

Complexity Analysis:

• Time Complexity: O(n)
  • As we traverse the list once.
• Space Complexity: O(1)
  • Since no extra space is used beyond a variable to store the result.