1290. Convert Binary Number in a Linked List to Integer

Problem Description

In this problem, we're given a singly-linked list that represents a binary number. Each node of the linked list contains a 0 or a 1, with the head of the list representing the most significant bit (MSB) of the binary number. We need to determine the decimal value represented by this binary number.

Intuition

The intuition behind the solution is that we can initialize an integer to hold our result and iterate over each node of the linked list from head to tail. As we move through each node, we perform two operations on the current result:

Left shift the current result by 1 bit. This is similar to multiplying the current decimal number by 2 in a binary system, effectively shifting all the bits to the left and making room for the next bit.
Use the bitwise OR operation to include the value of the current node (0 or 1) in the least significant bit (LSB) of our current result.

By repeatedly applying these two steps for each node, we can build up the decimal value bit by bit from the binary representation in the linked list.

Learn more about Linked List and Math patterns.

Solution Approach

The implementation of the solution directly reflects the intuition behind the approach. Here, we use bitwise operations which are a very efficient way to handle binary numbers.

Initialize an integer ans to 0 which will eventually contain the decimal value of the binary number.
Start a while loop that will continue as long as there is a node in the linked list (while head:).
Within the loop, update ans using the left shift (<<) operator. Shifting ans by one bit to the left (ans << 1) is equivalent to multiplying the current ans by 2 (in binary representation, this adds a new bit set to 0 at the end).
Perform a bitwise OR (|) with the value of the current node (head.val). Since head.val is either 0 or 1, using | will set the new least significant bit of ans to the value of the current node.
Move on to the next node (head = head.next).
Once we've iterated over all nodes, the loop ends, and we return ans, which now stores the decimal value of the binary number represented by the linked list.

The algorithm uses a single pass to convert the binary number to decimal, making the time complexity O(n) where n is the number of nodes in the linked list. No extra space other than the variable ans is used, resulting in a space complexity of O(1).

The data structure used here is the given singly-linked list, and the pattern followed is essentially bit manipulation to convert from binary to decimal efficiently.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Imagine we have a singly-linked list representing the binary number 1011, which looks like this:

1 -> 0 -> 1 -> 1

Where the head of the list represents the most significant bit (MSB).

Here are the steps to compute the decimal value of this binary:

Initialize an integer ans to 0.
The head points to the first node containing 1, start the while loop.
Left shift ans by 1 bit, resulting in ans = 0 << 1 = 0.
Perform a bitwise OR with the value of the current node (ans | head.val), resulting in ans = 0 | 1 = 1.
Move on to the next node, which contains 0.
Left shift ans by 1 bit, resulting in ans = 1 << 1 = 2.
Perform a bitwise OR with the value of the current node (ans | head.val), resulting in ans = 2 | 0 = 2.
Move on to the next node, which contains 1.
Left shift ans by 1 bit, resulting in ans = 2 << 1 = 4.
Perform a bitwise OR with the value of the current node (ans | head.val), resulting in ans = 4 | 1 = 5.
Move on to the last node, which contains 1.
Left shift ans by 1 bit, resulting in ans = 5 << 1 = 10.
Perform a bitwise OR with the value of the current node (ans | head.val), resulting in ans = 10 | 1 = 11.

After iterating over all the nodes, we conclude that the decimal value of the binary number 1011 is 11. The while loop ends and we return ans, which now contains the correct decimal value.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7class Solution:
8    def getDecimalValue(self, head: ListNode) -> int:
9        # Initialize the result variable to 0.
10        result = 0
11      
12        # Traverse the linked list.
13        while head:
14            # Bitwise left shift result by 1 (equivalent to multiplying by 2)
15            # and perform bitwise OR with the current node's value
16            # to append it to the binary number we are building.
17            result = (result << 1) | head.val
18          
19            # Move to the next node in the linked list.
20            head = head.next
21      
22        # Return the final decimal value of the binary number.
23        return result
24

1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5    int val;
6    ListNode next;
7    ListNode() {}
8    ListNode(int val) { this.val = val; }
9    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
10}
11
12class Solution {
13    /**
14     * Gets the decimal value of a binary number represented as a singly-linked list,
15     * where each node contains a binary digit. The most significant bit is at the head of the list.
16     *
17     * @param head The head of the singly-linked list representing the binary number.
18     * @return The integer decimal value of the binary number.
19     */
20    public int getDecimalValue(ListNode head) {
21        int number = 0; // Initialize a variable to store the decimal number.
22
23        // Iterate through each node of the list until the end is reached.
24        while (head != null) {
25            // Left-shift 'number' by 1 bit to make space for the new bit, and then
26            // combine it with the current node's value using bitwise OR operation.
27            number = (number << 1) | head.val;
28
29            // Move to the next node in the list.
30            head = head.next;
31        }
32      
33        // Return the decimal number that is represented by the binary list.
34        return number;
35    }
36}
37

1// Definition for singly-linked list.
2struct ListNode {
3  int val; // Value of the node
4  ListNode *next; // Pointer to the next node
5  ListNode() : val(0), next(nullptr) {} // Constructor initializes node with 0
6  ListNode(int x) : val(x), next(nullptr) {} // Constructor initializes node with given value
7  ListNode(int x, ListNode *next) : val(x), next(next) {} // Constructor initializes node with given value and next pointer
8};
9
10class Solution {
11public:
12    // Function to convert a binary number in a linked list to an integer.
13    int getDecimalValue(ListNode* head) {
14        int result = 0; // This will hold the decimal value of the binary number
15
16        // Iterate through the linked list
17        while (head != nullptr) {
18            // Left shift the result by 1 bit to make space for the next bit
19            // Then perform a bitwise OR with the current node's value to add the bit to the number
20            result = (result << 1) | head->val;
21
22            // Move to the next node
23            head = head->next;
24        }
25        // Return the computed decimal value
26        return result;
27    }
28};
29

1// TypeScript definition for a node in a singly-linked list.
2interface ListNode {
3    val: number;
4    next: ListNode | null;
5}
6
7/**
8 * This function calculates the decimal value of a binary number represented
9 * as a singly-linked list, where each node contains a single digit.
10 * The digits are stored in reverse order, meaning the head of the list
11 * represents the least significant bit.
12 *
13 * @param {ListNode | null} head - The head of the singly-linked list.
14 * @return {number} - The decimal value of the binary number.
15 */
16function getDecimalValue(head: ListNode | null): number {
17    // Initialize answer as 0 to prepare for binary to decimal conversion.
18    let decimalValue = 0;
19  
20    // Traverse the linked list starting from the head until the end.
21    while (head !== null) {
22        // Left shift the current decimal value by 1 bit (equivalent to multiplying by 2)
23        // to make space for the next binary digit, and then use bitwise OR to add 
24        // the value of the current node (either 0 or 1) to the least significant bit of the answer.
25        decimalValue = (decimalValue << 1) | head.val;
26      
27        // Move to the next node in the list.
28        head = head.next;
29    }
30  
31    // Return the computed decimal value after traversing the entire list.
32    return decimalValue;
33}
34

Time and Space Complexity

The provided code snippet defines a method getDecimalValue that converts a binary number represented by a linked list to its decimal value. Let's analyze the time complexity and space complexity.

Time Complexity:

The time complexity of the function is determined by the while loop that iterates once for each element in the linked list. Inside the while loop, the operations performed (bit shift and bitwise OR) are constant time operations, which means they take O(1) time. If there are n elements in the linked list, the loop runs n times. Therefore, the time complexity is O(n).

Space Complexity:

As for the space complexity, the function only uses a fixed number of variables (ans and head) regardless of the input size. There are no additional data structures used that grow with the size of the input. Hence, the space complexity is O(1), which is constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know