Algorithms 101: Adding Two Numbers Represented by Linked Lists

两个链表相加

This problem involves adding two numbers represented by two linked lists. Each linked list stores a non-negative integer where the digits are stored in reverse order, meaning that the least significant digit comes first. Each node in the linked list contains a single digit, and the task is to add the two numbers and return the sum as a new linked list, which should also represent the number in reverse order.

这个问题涉及到将两个由链表表示的数字相加。每个链表存储一个非负整数，其中数字按逆序存储，即最低有效位在前。链表中的每个节点包含一个数字，任务是将这两个数相加，并以链表的形式返回和，和链表也应表示为逆序。

1. Problem Description

问题描述

Given two non-empty linked lists representing two non-negative integers, add the two numbers and return the sum as a linked list. The digits are stored in reverse order, and each of their nodes contains a single digit. You may assume the two numbers do not contain any leading zeros, except for the number 0 itself.

给定两个非空链表，表示两个非负整数，将这两个数字相加并以链表形式返回和。数字按逆序存储，每个节点包含一个数字。你可以假设这两个数除了数字 0 之外，不会以 0 开头。

Example

示例

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807, and the linked list representation is in reverse order.

输入: l1 = [2,4,3], l2 = [5,6,4]
输出: [7,0,8]
解释: 342 + 465 = 807，链表表示为逆序。

Constraints

约束条件

The number of nodes in each linked list is in the range [1, 100].
Each node contains a single digit, 0 <= Node.val <= 9.
The numbers represented by the linked lists do not contain leading zeros except the number 0 itself.
每个链表中的节点数量在 [1, 100] 范围内。
每个节点包含一个数字，0 <= Node.val <= 9。
链表表示的数字不包含前导零，除了数字 0 本身。

2. Algorithm Analysis

算法分析

The problem can be solved by simulating the process of adding two numbers digit by digit, just as we do with pen and paper. We start from the least significant digit (the head of the linked list) and move towards the most significant digit, taking care to handle any carry from one digit to the next.

这个问题可以通过模拟逐位相加的过程来解决，就像我们用纸和笔做加法一样。我们从最低有效位（链表的头部）开始，逐位向前移动，同时注意处理每位的进位。

Core Idea

核心思路

Initialize a dummy node to act as the starting point for the result linked list.
Use a pointer to keep track of the current position in the result list.
Use a carry variable to keep track of any carry-over from the previous digit addition.
Traverse both linked lists simultaneously:
- If a list is shorter, consider missing nodes as 0.
- Add the corresponding digits from both lists along with the carry.
- Update the carry for the next iteration.
- Create a new node with the result digit and link it to the result list.
If there is a carry left after the final addition, create an additional node.
Return the result linked list, which starts from the node following the dummy node.
初始化一个虚拟节点，作为结果链表的起始点。
使用一个指针跟踪结果链表中的当前位置。
使用 carry 变量来跟踪前一位相加的进位。
同时遍历两个链表：
- 如果一个链表较短，缺少的节点视为 0。
- 将两个链表中的对应数字加上进位。
- 更新下一次迭代的进位。
- 创建一个包含结果数字的新节点，并将其链接到结果链表中。
如果在最终相加后还有进位，创建一个额外的节点。
返回结果链表，从虚拟节点的下一个节点开始。

Code Implementation

代码实现

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

def addTwoNumbers(l1, l2):
    dummy = ListNode()  # Initialize the dummy node
    current = dummy     # Pointer to construct the new list
    carry = 0           # Initialize carry to 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0  # Value from l1 or 0 if l1 is None
        val2 = l2.val if l2 else 0  # Value from l2 or 0 if l2 is None

        # Calculate the sum of the two digits and the carry
        total = val1 + val2 + carry
        carry = total // 10          # Update carry
        new_val = total % 10         # Get the digit to store

        # Create a new node with the sum and move the pointer
        current.next = ListNode(new_val)
        current = current.next

        # Move to the next nodes in l1 and l2 if they exist
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    # Return the next node after dummy (start of the actual list)
    return dummy.next

Detailed Explanation

详细解释

Initialization: A dummy node is created to simplify list operations. The current pointer is used to build the result list by adding nodes corresponding to the sum of digits from l1 and l2.
初始化：创建一个虚拟节点以简化链表操作。使用 current 指针通过添加对应于 l1 和 l2 数字之和的节点来构建结果链表。
Addition Process: The while loop continues as long as there are nodes in l1 or l2 or a carry value. In each iteration, we sum the corresponding digits and the carry, update the carry, and store the result digit in the new linked list node.
加法过程：只要 l1 或 l2 中有节点或有进位值，while 循环就会继续。在每次迭代中，我们将对应的数字和进位相加，更新进位，并将结果数字存储在新的链表节点中。
Handling Remaining Nodes and Carry: After processing all nodes, if there is a remaining carry, it is added as a new node at the end of the result list.
处理剩余节点和进位：在处理完所有节点后，如果还有剩余进位，则将其作为新节点添加到结果链表的末尾。
Return Statement: Finally, the result linked list is returned, starting from the node next to the dummy node.
返回语句：最后，返回结果链表，从虚拟节点的下一个节点开始。

Time Complexity Analysis

时间复杂度分析

The time complexity of this algorithm is O(max(n, m)), where n and m are the lengths of l1 and l2, respectively. This is because we process each node from both lists exactly once.

该算法的时间复杂度为 O(max(n, m))，其中 n 和 m 分别是 l1 和 l2 的长度。这是因为我们分别处理两个链表中的每个节点一次。

3. Conclusion

结论

Adding two numbers represented by linked lists involves careful digit-by-digit addition, taking into account the carry from each operation. The iterative approach is straightforward and ensures that all digits are processed correctly, resulting in a new linked list that represents the sum of the two numbers in reverse order. This method is efficient and easy to implement, making it a reliable solution for this common problem.

将由链表表示的两个数字相加需要逐位相加，考虑到每次操作的进位。迭代方法简单明了，确保所有数字都被正确处理，最终得到的链表表示两个数字之和的逆序。该方法高效且易于实现，使其成为解决这一常见问题的可靠方案。

Post Views: 50

CODEBITWAVE