Skip to main content

1290. Convert Binary Number in a Linked List to Integer

easy

A singly-linked list holds the binary digits of an integer, most-significant first. Convert to decimal in one pass using shift-and-OR.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Walk the list once. At each node, you don't know the final exponent — but you can avoid that with the running-shift trick.

Hint 2

Initialize result = 0. For each node: result = (result << 1) | node.val.

Hint 3

After processing all nodes, result holds the decimal value. This works because each new bit becomes the lowest bit and previous bits shift up by one.

Solution approach

Reveal approach

Shift-and-OR walk. Initialize result = 0 and curr = head. While curr is not null: result = (result << 1) | curr.val; curr = curr.next. Return result. The shift-left-by-one effectively multiplies the accumulator by 2 (the base), and the OR'd-in lowest bit appends curr.val as the next digit. This is the standard algorithm for converting a most-significant-first digit stream into an integer in any base — for binary it's especially neat because << and | replace the *= and += of a general base-b conversion. O(n) time over the n list nodes, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • bit-manipulation
  • linked-list

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Convert Binary Number in a Linked List to Integer and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →