algoadvance

Leetcode 1290. Convert Binary Number in a Linked List to Integer

Problem Statement

  1. Convert Binary Number in a Linked List to Integer

Given the head of a singly linked list where each node contains a single binary digit (0 or 1), return the decimal value of the number in the linked list.

Example:

Clarifying Questions

  1. Q: Can the linked list be empty? A: No, the problem guarantees at least one node in the linked list.
  2. Q: Are there limits on the length of the linked list? A: The length of the linked list is between 1 and 30.
  3. Q: Can the linked list contain values other than 0 and 1? A: No, each node will only contain 0 or 1 as per the problem description.

Strategy

  1. Traverse the linked list.
  2. Convert the binary number represented by the linked list to a decimal number:
    • Initialize a variable to store the result as 0.
    • For each node, shift the result to the left by 1 (equivalent to multiplying by 2) and add the current node’s value.
  3. Return the resultant decimal value.

Code

#include <iostream>

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

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int result = 0;
        ListNode* current = head;
        
        while (current != nullptr) {
            result = (result << 1) | current->val;  // Shift left and add current node's value
            current = current->next;
        }
        
        return result;
    }
};

int main() {
    // Example usage:
    Solution solution;
    
    // Creating the linked list [1,0,1]
    ListNode* head = new ListNode(1);
    head->next = new ListNode(0);
    head->next->next = new ListNode(1);
    
    // Output should be 5
    std::cout << "Decimal Value: " << solution.getDecimalValue(head) << std::endl;

    // Freeing the linked list
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    
    return 0;
}

Time Complexity

The time complexity of this function is O(n) where n is the number of nodes in the linked list. This is because we need to traverse the entire linked list once to compute the decimal value.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI