LeetCode: 2 Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

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

Example

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

问题

给定两个非空的链表，它们表示两个非负整数。数字以逆序存储，并且它们的每个节点都包含一个数字。将两个数字相加并将结果作为链表返回。

你可以假设这两个数字不包含任何前导零，除了数字0本身。

例子

输入: l1 = [2,4,3], l2 = [5,6,4]
输出: [7,0,8]
解释: 342 + 465 = 807。

Solution

Approach: Iterative Addition / 迭代相加

To add the two numbers represented by two linked lists, we can traverse both lists simultaneously, adding corresponding digits along with any carry from the previous digit.
If the sum is greater than 9, we store the carry and proceed to the next digit.

Approach Explanation

Carry Management: Use a variable carry to keep track of any carry value from the previous addition.
Node Traversal: Traverse both linked lists, adding corresponding digits, and if one list is shorter, treat missing digits as 0.
Result Storage: Store the result in a new linked list, creating nodes as you go.

Iterative Process

sum = l1.val + l2.val + carry
carry = sum // 10
result_node = sum % 10

Implementation

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        carry = 0
        dummy = ListNode()
        current = dummy

        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            total = val1 + val2 + carry
            carry = total // 10
            current.next = ListNode(total % 10)
            current = current.next

            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        return dummy.next

Explanation

Initialize Variables / 初始化变量
```
carry = 0
dummy = ListNode()
current = dummy
```
- English: We initialize carry to track any carry value from the addition, and dummy to help build the resulting linked list.
- Chinese: 我们初始化 carry 来追踪相加时的进位值，使用 dummy 来构建结果链表。
Traverse Both Linked Lists / 遍历两个链表
```
while l1 or l2 or carry:
   val1 = l1.val if l1 else 0
   val2 = l2.val if l2 else 0
```
- English: We iterate while there are nodes to process in either list or there’s a carry. We take the current node values or 0 if a list is shorter.
- Chinese: 我们在任一链表还有节点或有进位时进行迭代。我们取当前节点的值，若链表较短，则取 0。
Calculate Sum and Carry / 计算和与进位
```
total = val1 + val2 + carry
carry = total // 10
current.next = ListNode(total % 10)
```
- English: We calculate the sum of the current digits and the carry, then compute the new carry and store the remainder as the current node value.
- Chinese: 我们计算当前数字与进位的总和，然后计算新的进位，并将余数存为当前节点的值。
Move to Next Nodes / 移动到下一个节点
```
current = current.next
if l1:
   l1 = l1.next
if l2:
   l2 = l2.next
```
- English: We move the pointer to the next node in the result list and proceed to the next nodes in both input lists if available.
- Chinese: 我们将指针移动到结果链表的下一个节点，并处理两个输入链表的下一个节点（如果有的话）。
Return the Result / 返回结果
```
return dummy.next
```
- English: Finally, we return the resulting list starting from dummy.next, skipping the initial dummy node.
- Chinese: 最后，我们返回从 dummy.next 开始的结果链表，跳过初始的虚拟节点。

Complexity Analysis

Time Complexity / 时间复杂度: O(max(m, n)), where m and n are the lengths of the two input lists. We traverse both lists fully.
Space Complexity / 空间复杂度: O(max(m, n)), since we create a new linked list with the same number of nodes as the longer input list.

Key Concept

Carry Propagation / 进位传播: In addition, carry must be handled correctly, as it can propagate across digits.
Linked List Traversal / 链表遍历: We traverse both linked lists in parallel, handling different lengths by treating missing digits as zero.

Summary

English: The problem is solved by iterating over both linked lists, summing corresponding digits, and handling carry propagation. The result is returned as a new linked list.
Chinese: 通过遍历两个链表，相加相应的数字，并处理进位传播来解决问题。结果以新的链表形式返回。

Tips

English: Understanding how to traverse linked lists and manage carry operations is key in this problem.
Chinese: 理解如何遍历链表和管理进位操作是解决这个问题的关键。

5 More Similar Questions

Recommended Resources

English: Practice problems involving linked lists and carry management to become comfortable with linked list manipulation and addition operations.
Chinese: 练习涉及链表和进位管理的问题，以熟悉链表操作和加法运算。

Post Views: 13

CODEBITWAVE