Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-ll
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
"""
Naive Solution(如果你不懂binary representation)
step1: reverse the linked list
step2: travser the linked list and progressivly build the res
Optimal Solution:
step1: traverse the linked list. During the traversal, use binary representation
num = num*2 + x(current val)
101
num = 1
num = 1*2+0 = 2
num = 2*2+1 = 5
"""
def getDecimalValue(self, head: ListNode) -> int:
reversed_head = self.get_reversed_ll(head)
cur = reversed_head
res = 0
count = 0
while cur:
res += 2**count * cur.val
count+=1
cur = cur.next
return res
def get_reversed_ll(self, head):
d = ListNode(-1)
d.next = head
cur = head.next
head.next = None
while cur:
nxt = cur.next
cur.next = d.next
d.next = cur
cur = nxt
return d.next
def getDecimalValue(self, head: ListNode) -> int:
num = head.val
cur = head.next
while cur:
num = num*2 + cur.val
cur = cur.next
return num
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment