LinkedList添加两个数字: LeetCode

问题描述： 给定两个非空的链表，表示两个非负的整数。链表中的每个节点都包含一个0-9的数字，数字按照逆序的方式存储，并且每个节点只能存储一位数字。将这两个链表相加，并且返回一个新的链表。

示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 解释：342 + 465 = 807

解答： 这个问题可以通过模拟加法的方式来解决。我们可以创建一个新的链表，然后从头开始遍历两个输入链表，将对应位置的数字相加，并且考虑进位。具体的步骤如下：

1. 创建一个新的链表，用于存储相加的结果。
2. 初始化两个指针，分别指向两个输入链表的头节点。
3. 初始化一个进位变量carry，初始值为0。
4. 遍历两个链表，直到两个链表都遍历完为止：
   • 获取当前节点的值，如果节点为空，则值为0。
   • 计算当前位置的和，即两个节点的值相加再加上进位。
   • 更新进位，如果和大于等于10，则进位为1，否则为0。
   • 创建一个新的节点，值为和对10取余的结果。
   • 将新节点添加到结果链表中。
   • 更新指针，将指针指向下一个节点。

• 如果遍历完后，进位仍然为1，则需要在结果链表末尾添加一个值为1的节点。
• 返回结果链表。

这个问题可以使用Java语言来实现，以下是一个示例代码：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;
        
        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        
        return dummy.next;
    }
}

在这个解法中，我们使用了一个虚拟头节点(dummy)来简化代码。通过遍历两个输入链表，我们可以将对应位置的数字相加，并且考虑进位。最后，我们返回结果链表的下一个节点，即为最终的结果。

推荐的腾讯云相关产品和产品介绍链接地址：

• 云服务器（CVM）：https://cloud.tencent.com/product/cvm
• 云数据库 MySQL 版（CDB）：https://cloud.tencent.com/product/cdb
• 云原生应用引擎（TKE）：https://cloud.tencent.com/product/tke
• 人工智能机器学习平台（AI Lab）：https://cloud.tencent.com/product/ailab
• 物联网开发平台（IoT Explorer）：https://cloud.tencent.com/product/iothub
• 移动应用开发平台（MPS）：https://cloud.tencent.com/product/mps
• 云存储（COS）：https://cloud.tencent.com/product/cos
• 区块链服务（BCS）：https://cloud.tencent.com/product/bcs
• 腾讯元宇宙（Tencent Metaverse）：https://www.tencent.com/en-us/industries/metaverse