LeetCode: 445. Add Two Numbers II

题目

原题地址：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

Comments