LeetCode：2. Add Two Numbers（计算两个数的和）

阳光穿透心脏的1/2处 2022-04-11 02:20 162阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。
> 
> 这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

### 题目描述： ###

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

来源：力扣（LeetCode）

--------------------

### java实现方法1： ###

/**
         * 两个链表相加
         *
         * @param l1 链表1
         * @param l2 链表2
         * @return 链表结果
         */
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode node = new ListNode(-1);
            ListNode dummy= node;
            int carry = 0;
            while (l1 != null || l2 != null) {
                int num1 = l1 == null ? 0 : l1.val;
                int num2 = l2 == null ? 0 : l2.val;
                int total = num1 + num2 + carry;
                carry = total / 10;
                node.next = new ListNode(total % 10);
                if (l1 != null) {
                    l1 = l1.next;
                }
                if (l2 != null) {
                    l2 = l2.next;
                }
                node = node.next;
            }
            if (carry > 0) {
                node.next = new ListNode(carry);
            }
            return dummy.next;
        }

时间复杂度：O(n+m)

空间复杂度：O(n+m)

--------------------

### python实现方法1： ###

def add_two_number(self, l1: ListNode, l2: ListNode) -> ListNode:
            '''
                两个链表相加
            Args:
                l1: 链表l1
                l2: 链表l2
            Returns:
                链表的和
            '''
            node = ListNode(-1)
            dummy= node
            carry = 0
            while l1 or l2:
                num1 = 0 if not l1 else l1.val
                num2 = 0 if not l2 else l2.val
                total = num1 + num2 + carry
                node.next = ListNode(total % 10)
                node = node.next
                carry = total // 10
                if l1:
                    l1 = l1.next
                if l2:
                    l2 = l2.next
            if carry > 0:
                node.next = ListNode(carry)
            return dummy.next

时间复杂度：O(n+m)

空间复杂度：O(n+m)

--------------------

### Java实现方法2： ###

/**
         * 两个链表相加
         *
         * @param l1 链表1
         * @param l2 链表2
         * @return 链表结果
         */
        public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            return this.addTwoNumberList(l1, l2, 0);
        }
        /**
         * 两个链表相加
         *
         * @param l1 链表1
         * @param l2 链表2
         * @param v  数字v
         * @return 返回合并后链表
         */
        private ListNode addTwoNumberList(ListNode l1, ListNode l2, int v) {
            if (l1 == null && l2 == null) {
                return v == 0 ? null : new ListNode(v);
            }
            if (l1 != null) {
                v += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                v += l2.val;
                l2 = l2.next;
            }
            return new ListNode(v % 10, addTwoNumberList(l1, l2, v / 10));
        }

时间复杂度：O(n+m)

空间复杂度：O(n+m)

--------------------

### Python实现方法2： ###

def add_two_number2(self, l1: ListNode, l2: ListNode) -> ListNode:
            '''
                两个链表相加
            Args:
                l1: 链表l1
                l2: 链表l2
            Returns:
                链表的和
            '''
            if not l1:
                return l2
            if not l2:
                return l1
            return self.add_two_number_helper(l1, l2, 0)
    
        def add_two_number_helper(self, l1: ListNode, l2: ListNode, v: 0) -> ListNode:
            '''
                相加帮助类
            Args:
                l1: l1链表
                l2: l2链表
                v: 值
            Returns:
                链表
            '''
            if not l1 and not l2:
                return None if v == 0 else ListNode(v)
            if l1:
                v += l1.val
                l1 = l1.next
            if l2:
                v += l2.val
                l2 = l2.val
            return ListNode(v % 10, self.add_two_number_helper(l1, l2, v / 10))

时间复杂度：O(n+m)

空间复杂度：O(n+m)

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode