[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.

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:

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

Interesting in any computer science.