[LeetCode]#1290. Convert Binary Number in a Linked List to Integer

Environment: Python 3.7

Key technique: linked list

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

Analysis:

leetcode had definition for singly-linked list and we don’t need write IO for linked list. However, it is still linked list class for local test. This is my first time to do this data structure. So I need below class.

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class LinkList:
    def __init__(self):
        self.head=None
def initList(self, data):
        # Creat head node
        self.head = ListNode(data[0])
        r=self.head
        p = self.head
        # Create node for every data
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r
    def printlist(self,head):
        if head == None: return
        node = head
        while node != None:
            #print(node.val,end=' ')
            node = node.next

Moreover, follow below steps.

1. Convert n to list-node.
2. Calculate binary to decimal based on location.

Solution:

class Solution:
    def getDecimalValue(self, head):
        t, node_n=head, 0
        while(t):
            node_n+=1
            t=t.next
        sum_n=0
        for i in range(node_n):
            x=head.val
            sum_n+=x*2**(node_n-1-i)
            head=head.next
        return sum_n

Submitted result:

Lesson learn:

This is first time to solve this data structure and spend two day to understand.

Reference:

Python--链表的输入输出代码,python

https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/discuss/568928/Python-Time-97.69-Memory-100