"""
Solution for 1290. Convert Binary Number in a Linked List to Integer
https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/
"""


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
  """
  Runtime: 24 ms, faster than 100.00% of Python3 online submissions for Convert Binary Number in a Linked List to Integer.
  Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Convert Binary Number in a Linked List to Integer.
  """
  def initial_solution(self, head: ListNode) -> int:
    """
    An initial solution that uses built-in int function to convert the string
    representation into base 10 number. This runs in O(N) in time and O(N) in
    space

    Args:
      head:

    Returns:

    """
    binary = ''
    while head:
      binary += str(head.val)
      head = head.next
    return int(binary, 2)

  def optimal_solution(self, head: ListNode) -> int:
    """
    An optimal solution that runs in O(N) in time and O(1) in space

    Args:
      head:

    Returns:

    """
    ans = 0
    while head:
      ans = (ans * 2) + head.val
      head = head.next
    return ans

  def bit_solution(self, head: ListNode) -> int:
    ans = 0
    while head:
      ans = (ans << 1) + head.val
      head = head.next
    return ans

  def getDecimalValue(self, head: ListNode) -> int:
    """
    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 0 or 1.

    Args:
      head:

    Returns:

    """
    return self.optimal_solution(head)