Python 中用链表表示数字的程序

假设我们有两个单链表 L1 和 L2，每个链表都表示一个数字，最低有效位在前，我们需要找到它们的和表示的链表。

因此，如果输入类似于 L1 = [5,6,4] L2 = [2,4,8]，则输出将是 [7, 0, 3, 1, ]

为了解决这个问题，我们将遵循以下步骤

• 进位 := 0

• 结果 := 一个值为 0 的新节点

• 当前 := 结果

• 当 L1 不为空或 L2 不为空或进位不为零时，执行以下操作

  • l0_val := L1 的值，如果 L1 不为空，否则为 0

  • l1_val := L2 的值，如果 L2 不为空，否则为 0

  • 总和 := l0_val + l1_val

  • 进位 := (总和 + 进位) / 10 的商

  • 加值 := (总和 + 进位) / 10 的余数

  • 当前.next := 一个值为加值的新节点

  • 当前 := 当前的下一个节点

  • L1 := L1 的下一个节点，如果 L1 不为空，否则为 null

  • L2 := L2 的下一个节点，如果 L2 不为空，否则为 null

• 当前的下一个节点 := null

• 返回结果的下一个节点

让我们看看下面的实现以更好地理解

示例

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

def print_list(head):
   ptr = head
   print('[', end = "")
   while ptr:
      print(ptr.val, end = ", ")
      ptr = ptr.next
   print(']')

class Solution:
   def solve(self, L1, L2):
      carry = 0
      res = ListNode(0)
      curr = res

      while L1 or L2 or carry:
         l0_val = L1.val if L1 else 0
         l1_val = L2.val if L2 else 0
         sum_ = l0_val + l1_val
         carry, add_val = divmod(sum_ + carry, 10)

         curr.next = ListNode(add_val)
         curr = curr.next

         L1 = L1.next if L1 else None
         L2 = L2.next if L2 else None

      curr.next = None

return res.next

ob = Solution()
L1 = make_list([5,6,4])
L2 = make_list([2,4,8])
print_list(ob.solve(L1, L2))

输入

[5,6,4], [2,4,8]

输出

[7, 0, 3, 1, ]

Arnab Chakraborty

更新于: 2020-11-09

100 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习