1290. Convert Binary Number in a Linked List to Integer

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.

Example 1

Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10

Example 2

Input: head = [0]
Output: 0

Key Insight

The solution leverages the fact that binary numbers can be converted to decimal by traversing the linked list and accumulating the result:

1. Start with result = 0
2. For each node in the linked list:
   • Left shift result by 1 (equivalent to multiplying by 2)
   • Add the current node's value to the result
3. Return the accumulated result

Approach 1: Linear Traversal with Bit Shifting

This approach directly converts the binary linked list to decimal by traversing the list once.

Algorithm Steps

1. Initialize result to 0
2. Traverse the linked list from head to tail:
   • Left shift result by 1 (result = result * 2)
   • Add current node's value to result (result += node.val)
3. Return the final result

/**
 * 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) {
        int result = 0;
        while (head != nullptr) {
            result = (result << 1) | head->val;
            head = head->next;
        }
        return result;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        int result = 0;
        while (head != null) {
            result = (result << 1) | head.val;
            head = head.next;
        }
        return result;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        result = 0
        while head:
            result = (result << 1) | head.val
            head = head.next
        return result

Approach 2: String Conversion

This approach converts the binary linked list to a string first, then converts the string to decimal.

Algorithm Steps

1. Traverse the linked list and build a binary string
2. Convert the binary string to decimal using built-in functions
3. Return the decimal value

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        string binary;
        while (head != nullptr) {
            binary += to_string(head->val);
            head = head->next;
        }
        return stoi(binary, 0, 2);
    }
};

class Solution {
    public int getDecimalValue(ListNode head) {
        StringBuilder binary = new StringBuilder();
        while (head != null) {
            binary.append(head.val);
            head = head.next;
        }
        return Integer.parseInt(binary.toString(), 2);
    }
}

class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        binary = ''
        while head:
            binary += str(head.val)
            head = head.next
        return int(binary, 2)

Approach Comparison

Edge Cases

1. Single node with value 0

Input: [0] → Output: 0

2. Single node with value 1

Input: [1] → Output: 1

3. All zeros

Input: [0,0,0] → Output: 0

4. All ones

Input: [1,1,1] → Output: 7

5. Maximum length (30 nodes)

Input: [1,1,...,1] (30 times) → Output: 2^30 - 1

Frequently Asked Questions