LeetCode: 445. Add Two Numbers II

3 years ago

source link: https://mozillazg.com/2020/09/leetcode-445-add-two-numbers-ii.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目¶

原题地址：https://leetcode.com/problems/add-two-numbers-ii/

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

解法¶

这个问题是前面 LeetCode: 2. Add Two Numbers 那个问题的增强版，主要是需要反向计算以及反向构建链表。

反向遍历链表然后按照加法运算的规则计算各个节点的值¶

因为两个链表的节点表示的是高位到低位的值，但是加法运算一般是从低位到高位进行运算的，所以需要反向遍历两个链表然后对节点值做加法运算，再反向生成结果链表：

因为是单向链表无法快速反向遍历，可以通过正向遍历链表生成一个节点组成的栈，然后通过栈来实现反向遍历的需求。
因为是从低位到高位进行计算，所以结果也是从低位开始生成的，因此这里需要反向生成结果链表。

这个方法的 Python 代码类似下面这样:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1, l2):
        stack1 = []
        stack2 = []
        while l1 is not None:
            stack1.append(l1)
            l1 = l1.next
        while l2 is not None:
            stack2.append(l2)
            l2 = l2.next

        head = None
        carry = 0
        while stack1 or stack2 or carry > 0:
            l1_val = 0
            l2_val = 0
            if stack1:
                l1_val = stack1.pop().val
            if stack2:
                l2_val = stack2.pop().val

            total = l1_val + l2_val + carry
            carry = total // 10
            val = total % 10
            node = ListNode(val)
            node.next = head
            head = node

        return head

Recommend