สมมติว่ามี singly linked list ที่แทนตัวเลขฐานสอง โดยหลักสำคัญอยู่หน้าสุด เราต้องคืนค่าเป็นจำนวนเต็มฐานสิบ
เช่น ถ้าอินพุตคือ [1,0,1,1,0] ผลลัพธ์จะเป็น 22
ขั้นตอนการแก้ปัญหา
- l := รายการใหม่
- while node ไม่ใช่ null ใส่ค่าของ node เข้า l, node := next of node
- k := 0, v := 0
- for i จาก len(l)-1 ถึง 0 ถ้า l[i] == 1 v := v + 2^k, k := k + 1
- คืนค่า v
ตัวอย่างโค้ด
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))
อินพุต
[1,0,1,1,0]
เอาต์พุต
22
