Convert Binary Number in a Linked List…

1. Define the problem

Convert Binary Number in a Linked List to Integer

Every node of the list holds a 0 or a 1 . Read from the head to the tail, those digits spell a binary number. Return that number written the normal way, in base ten. The function takes a plain array of 0s and 1s, builds the linked list inside, and returns a single number. You cannot walk a linked list backwards, so build the answer front to back : start at 0, and for each digit double what you have so far and add the new digit. Doubling shifts everything one place left, which is exactly what reading another binary digit means.

Constraints

The list has between 1 and 30 nodes
Every node value is 0 or 1
The answer fits comfortably in a normal number

Example

Inputvalues = [1, 0, 1]

Output5

Explanation The list spells the binary number 101, which is 4 + 0 + 1 = 5 in base ten.

2. Know the words first

In plain terms

Binary number: A number written with only 0s and 1s. Each place is worth twice the place to its right, so 101 means 4 + 0 + 1 = 5.
Base ten: The everyday way of writing numbers, with digits 0 to 9 — what most programming languages print by default.
Most significant digit: The leftmost digit, worth the most. In this list it is the head, which is why reading front to back works so neatly.

3. Visualize the solution

Each cell is one node holding a single binary digit, head first

head1

#20

#31

#41

Statusinit

The list spells 1011 in binary; the running total starts at 0.

What happens in this step

list = 1 -> 0 -> 1 -> 1
total = 0

No digit has been read yet. The plan is one pass from the head to the tail.

Step 1 of 6

Steps to visualize

Start with a running total of 0.
The frame marks the digit you are reading right now.
Double the running total, then add the digit under the frame.
Doubling makes room for one more binary digit, the same way multiplying by ten does in base ten.
After the last node, the running total is the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Each cell is one node holding a single binary digit, head first

head1

#20

#31

#41

Statusinit

The list spells 1011 in binary; the running total starts at 0.

What happens in this step

list = 1 -> 0 -> 1 -> 1
total = 0

No digit has been read yet. The plan is one pass from the head to the tail.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function toList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    head = new ListNode(values[i], head);
  }
  return head;
}

function getDecimalValue(values) {
  const head = toList(values);
  let total = 0;

  for (let node = head; node !== null; node = node.next) {
    total = total * 2 + node.val;
  }

  return total;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`values = [1, 0, 1]`	`5`	example from the description
`values = [0]`	`0`	shortest possible list, value zero
`values = [1]`	`1`	shortest possible list, value one
`values = [0, 0, 1, 1]`	`3`	zeros at the front must not change the answer
`values = [1, 0, 1, 1]`	`11`	the list used in the step-by-step animation
`values = [1, 1, 1, 1, 1, 1, 1, 1]`	`255`	a longer list, eight ones in a row

Convert Binary Number in a Linked List to Integer