leetcode-ll

1290. Convert Binary Number in a Linked List to Integer.py

# 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