LeetCode_2. 两数相加

题目

image.png

https://leetcode-cn.com/problems/add-two-numbers/

思路

1. 模拟法

  • 思路分析

对于链表 l1 和 l2 ，将共同都有的部分相加，构造结果链表，之后取某个较长链表的剩余部分构造结果链表。
需要注意的是，对进位的处理。

  • 代码实现

    1. # Definition for singly-linked list.
    2. # class ListNode:
    3. #     def __init__(self, val=0, next=None):
    4. #         self.val = val
    5. #         self.next = next
    6. class Solution:
    7.   def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    8.       res=ListNode() # 该节点仅仅作为链表头使用，方便批量迭代处理
    9.       t=res # 可以移动的节点指针
    10.       carry=0 # 保存进位
    11.       while l1 is not None and l2 is not None:
    12.           value=l1.val+l2.val+carry 
    13.           carry=0 # 加完进位之后将carry重置为0
    14.           if value>=10: # 判断加和是否大于等于10
    15.               carry=1
    16.               value=value-10
    17.           # 申请新的节点，并赋值
    18.           t.next=ListNode() 
    19.           t=t.next
    20.           t.val=value
    21.           # 更新l1和l2指针
    22.           l1=l1.next
    23.           l2=l2.next
    24.       while l1 is None and l2 is not None:
    25.           t.next=ListNode()
    26.           t=t.next
    27.           value=l2.val+carry
    28.           carry=0
    29.           if value>=10:
    30.               carry=1
    31.               value=value-10
    32.           t.val=value
    33.           l2=l2.next
    34.       while l2 is None and l1 is not None:
    35.           t.next=ListNode()
    36.           t=t.next
    37.           value=l1.val+carry
    38.           carry=0
    39.           if value>=10:
    40.               carry=1
    41.               value=value-10
    42.           t.val=value
    43.           l1=l1.next
    44.       if carry==1:# 最后检测是否还有进位
    45.           t.next=ListNode()
    46.           t=t.next
    47.           t.val=1
    48.       return res.next

  • 代码精简的结果

思想在于视为在较短的链表后面逻辑上补 0，从而方便处理。

  1. class Solution:
  2.     def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
  3.         res=ListNode()
  4.         t=res
  5.         carry=0
  6.         while l1 or l2:
  7.             if l1:
  8.                 val1=l1.val
  9.                 l1=l1.next
  10.             else:
  11.                 val1=0
  12.             if l2:
  13.                 val2=l2.val
  14.                 l2=l2.next
  15.             else:
  16.                 val2=0
  17.             value=val1+val2+carry
  18.             t.next=ListNode(value%10)
  19.             t=t.next
  20.             carry=value//10
  21.         if carry>0:
  22.             t.next=ListNode(1)
  23.         return res.next

https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode-solution/