## 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 = 
Output: 0


Example 3:

Input: head = 
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 0 or 1.

## Solutions

题意简明，将链表表示的二进制转换为十进制。

### 1. Direct

# Time: O(n)
# Space: O(n)
class ListNode:
def __init__(self, x):
self.val = x
self.next = None

class Solution:
def getDecimalValue(self, head: ListNode) -> int:
queue = collections.deque()
n = len(queue)
value = 0
while queue and n > 0:
n -= 1
value += queue.popleft() * 2 ** n
return value

# 102/102 cases passed (28 ms)
# Your runtime beats 69.84 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)


### 2. O(1) space

# Time: O(n)
# Space: O(1)
class Solution:
def getDecimalValue(self, head: ListNode) -> int: