Convert Binary Number in a Linked List to Integer

Problem Statement

In this task, you are provided with the head node of a singly-linked list that represents a binary number with each node containing a binary digit (either '0' or '1'). The binary number is given such that the most significant bit (MSB) is at the head of the list, and this list structure deciphers the binary number from left to right, which is how we generally read numbers. The objective is to convert this binary representation directly from the linked list format into its decimal (base 10) numeric form.

Examples

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

Constraints

• The Linked List is not empty.
• Number of nodes will not exceed 30.
• Each node's value is either 0 or 1.

Approach and Intuition

Understanding how to approach the problem efficiently involves acknowledging a few key operations and concepts:

1. Since each node can be traversed only once in a singly-linked list and we cannot access any node directly (except by traversing), the conversion process involves reading and processing each node sequentially from the head to the end.
2. The most significant bit is at the head. This setup hints that if you start reading the linked list from the head, each subsequent node simply needs to be considered as the next least significant bit in the binary number.
3. As you read each node's value, you can build up the decimal value step-by-step. This can be accomplished efficiently using bit manipulation - specifically bit shifting.

Here's a visual breakdown using the examples provided:

• For example 1 (input head = [1,0,1]):

  • Start with an initial value 0 (let's call it num).
  • Read the first node (value 1), update num to 1 (num = 1 << 1 | 1 which simplifies to num = 1).
  • Read the second node (value 0), no change in value since 0 OR with any number remains unchanged (num = 1 << 1 | 0 equals 2, but OR with 0 does not alter it).
  • Read the third node (value 1), update num to 5 (num = 2 << 1 | 1 which equals 5).

• For example 2 (input head = [0]):

  • Start with initial value 0.
  • Only one node with value 0, so the resulting decimal value remains 0.

This conversion process is systematic and constant regardless of the binary number's length (as constrained by a maximum of 30 nodes), ensuring efficient computational time. Leveraging bitwise operations for constructing the number, as you traverse the linked list, gives a clear and direct approach to solving the problem.

Solutions

class Solution {
    public int convertBinaryToDecimal(ListNode node) {
        int decimal = node.val;
        while (node.next != null) {
            decimal = (decimal << 1) | node.next.val;
            node = node.next;
        }
        return decimal;
    }
}

class Solution:
    def binaryToDecimal(self, node: ListNode) -> int:
        binary_value = node.val
        while node.next:
            binary_value = (binary_value << 1) | node.next.val
            node = node.next
        return binary_value