Pythonでリンクリストとして表される数値を検索するプログラム

2つの単一リンクリストL1とL2があり、それぞれが最初に最下位桁の数字を表すと仮定すると、合計されたリンクリストを見つける必要があります。

したがって、入力がL1 =[5,6,4] L2 =[2,4,8]の場合、出力は[7、0、3、1、]

これを解決するには、次の手順に従います。

• キャリー：=0

• res：=値が0の新しいノード

• curr：=res

• L1が空でないか、L2が空でないか、キャリーがゼロ以外の場合は、実行してください

  • l0_val：=L1が空でない場合はL1の値。それ以外の場合は0

  • l1_val：=L2が空でない場合はL2の値。それ以外の場合は0

  • sum_：=l0_val + l1_val

  • キャリー：=（sum_ +キャリー）/ 10

    の商

  • add_val：=（sum_ +キャリー）の余り/ 10

  • curr.next：=値add_valの新しいノード

  • curr：=currの次

  • L1：=L1が空でない場合はL1の次、それ以外の場合はnull

  • L2：=L2が空でない場合はL2の次、それ以外の場合はnull

• 次のcurr：=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, ]