Scale Engineer

Convert Binary Number in a Linked List to Integer

Easy
#1202Time: O(N), where N is the number of nodes in the linked list. The traversal takes O(N) time, and parsing the string of length N also takes O(N) time.Space: O(N), for the `StringBuilder` which stores the N digits of the binary number.3 companies
Patterns
Math
Data structures
Linked List
Companies
RobloxMathWorksWorkday

Prompt

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

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves two main steps. First, we traverse the linked list to build a string representation of the binary number. Second, we use a built-in function to parse this binary string into its decimal integer equivalent.

Algorithm

  • Initialize a StringBuilder named sb.
  • Create a pointer current and set it to head.
  • Loop while current is not null:
    • Append current.val to sb.
    • Move current to current.next.
  • Convert the StringBuilder to a string.
  • Use Integer.parseInt(string, 2) to get the decimal value and return it.

Walkthrough

We initialize a StringBuilder to accumulate the digits. We iterate through the linked list from the head node to the end. In each step, we append the node's value (either '0' or '1') to the StringBuilder. After the traversal is complete, we will have a string like "101". Finally, we use Java's Integer.parseInt(binaryString, 2) method to convert this binary string into an integer. This method handles the conversion from base 2 to base 10 for us.

/** * 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) {        StringBuilder sb = new StringBuilder();        ListNode current = head;        while (current != null) {            sb.append(current.val);            current = current.next;        }        return Integer.parseInt(sb.toString(), 2);    }}

Complexity

Time

O(N), where N is the number of nodes in the linked list. The traversal takes O(N) time, and parsing the string of length N also takes O(N) time.

Space

O(N), for the `StringBuilder` which stores the N digits of the binary number.

Trade-offs

Pros

  • Simple to understand and implement, especially if you are familiar with string manipulation and built-in parsing functions.

Cons

  • Less efficient in terms of space, as it requires extra O(N) space to store the binary string.

  • The process of building a string and then parsing it can be slower than direct mathematical calculation due to overhead.

Solutions

/** * 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 ans = 0 ; for (; head != null ; head = head . next ) { ans = ans << 1 | head . val ; } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem