1290. Convert Binary Number in a Linked List to Integer
Description
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.
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
Example 3:
Input: head = [1] Output: 1
Example 4:
Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] Output: 18880
Example 5:
Input: head = [0,0] Output: 0
Constraints:
- The Linked List is not empty.
- Number of nodes will not exceed
30. - Each node's value is either
0or1.
My Solution
Source Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {number}
*/
var getDecimalValue = function(head) {
let num = 0;
let pointer = head;
while (pointer !== null) {
num = 2 * num + pointer.val;
pointer = pointer.next;
}
return num;
};
Analysis
When you convert a binary number to base 10 by hand, you usually start with the last digit and not the first. At least that's what I do anyway. But since these are stored as linked lists and the digits are in normal order, you can't do that. Instead another algorithm would consist of repeatedly multiplying by 2. It's literally the reverse of how you convert from base 10 to binary.
The running time is just O(n) where n is the number of digits in the binary number.