Chương trình chuyển đổi danh sách liên kết nhị phân sang số thập phân trong Python

Cho danh sách liên kết đơn biểu diễn số nhị phân (bit quan trọng nhất ở đầu), chuyển đổi thành số thập phân.

Ví dụ

Đầu vào: [1,0,1,1,0].
Đầu ra: 22.

Thuật toán

1. Duyệt danh sách liên kết, thu thập bit vào mảng l.
2. Khởi tạo k=0, v=0.
3. Duyệt l từ cuối về đầu: nếu bit == 1, v += 2^k; k++.
4. Trả về v.

Mã nguồn Python

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

class Solution:
    def solve(self, node):
        l = []
        while node:
            l.append(node.val)
            node = node.next
        k = 0
        v = 0
        for i in range(len(l)-1, -1, -1):
            if l[i] == 1:
                v += (2**k)
            k += 1
        return v

ob = Solution()
head = make_list([1,0,1,1,0])
print(ob.solve(head))

Đầu vào / Đầu ra

Input: [1,0,1,1,0]
Output: 22