algoadvance

We are given a singly linked list, where each node contains a single binary digit (0 or 1). Our goal is to convert this binary number represented by the linked list into an integer.

The linked list format is as follows:

• Each node contains a val attribute, which is either 0 or 1.
• Each node also contains a next attribute, which points to the next node in the linked list or None if it is the last node.

Clarifying Questions

1. Q: What is the maximum length of the linked list?
   • A: The problem does not specify, but linked list operations need to handle up to the maximum constraint typically handled in Python.
2. Q: Can the linked list be empty?
   • A: No, according to the problem constraints, the linked list will contain at least one node.
3. Q: Is the number provided by the linked list always valid in a binary form?
   • A: Yes, each node only contains a 0 or 1.

Strategy

1. Traverse the Linked List: Iterate through the linked list to retrieve the binary digits.
2. Convert to Integer: As we traverse, we can convert the binary number to an integer using bit manipulation or string conversion.
3. Return the Integer: Finally, return the converted integer.

Code

Let’s implement the solution using a class definition for the nodes and the function to convert the binary number in a linked list to an integer.

# 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:
        # Initialize result
        num = 0
        
        current = head
        while current is not None:
            # Shift the current number to the left (multiply by 2)
            # Add the current node's value
            num = (num << 1) | current.val
            # Move to the next node
            current = current.next
        
        return num

Strategy Explanation

1. Initialize Result Variable (num): This will store the final integer value.
2. Traverse the List: Use a while loop to iterate through each node of the linked list.
3. Shift and Add:
   • Left shift the current value of num by 1 (equivalent to multiplying by 2).
   • Add the current node’s value (0 or 1) to num using the OR | operation.
4. Move to Next Node: Continue this process until all nodes are processed.
5. Return the Result: The variable num now contains the decimal value of the binary number represented by the linked list.

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. This is because we traverse each node exactly once.
• Space Complexity: O(1), as we are using only a few extra variables, and the space required does not depend on the input size.

This solution ensures efficient traversal and conversion from binary to decimal, leveraging bit manipulation for optimal performance.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?