LeetCode两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

这个问题是经典的“链表相加”问题。两个链表中的每个节点都存储一个数字，它们按照逆序存储，也就是说最低位数字存储在链表的头部。我们需要对链表中的数字进行逐位相加，并将结果也以链表的形式返回。

解题思路

我们可以使用逐位相加的方式来解决问题，并且需要考虑进位。

具体步骤

1. 遍历两个链表：

   • 我们从两个链表的头部开始，逐位相加两个数，同时考虑前一位的进位情况。
   • 如果当前位的和大于或等于10，则产生进位。

2. 进位处理：

   • 当两个链表都遍历完后，如果还有进位，需要在结果链表的最后再加上一个节点来存储该进位。

3. 特殊情况处理：

   • 如果某个链表比另一个链表长，则在较短链表遍历完后，只需继续将长链表的剩余部分与进位相加。

4. 返回结果链表：

   • 结果链表也是按照逆序存储的形式输出。

Java代码实现

// 定义链表节点
class ListNode {
    int val;  // 节点的值
    ListNode next;  // 指向下一个节点的指针
    
    // 构造函数
    ListNode(int val) {
        this.val = val;
    }
}

public class AddTwoNumbers {
    
    /**
     * 将两个链表表示的数字相加，并返回结果链表
     *
     * @param l1 链表1
     * @param l2 链表2
     * @return 结果链表
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0); // 虚拟头节点
        ListNode curr = dummyHead;
        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 dummyHead.next; // 返回结果链表的头节点
    }

    public static void main(String[] args) {
        // 创建链表1: 2 -> 4 -> 3 表示数字342
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        // 创建链表2: 5 -> 6 -> 4 表示数字465
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        // 调用addTwoNumbers方法
        ListNode result = addTwoNumbers(l1, l2);
    }
}

代码解释

1. ListNode 类：

   • ListNode 是一个简单的链表节点类，每个节点包含一个整数 val 和一个指向下一个节点的指针 next。

2. addTwoNumbers 方法：

   • 该方法接收两个链表 l1 和 l2，表示两个逆序存储的数字。
   • dummyHead 是一个虚拟头节点，它的目的是简化链表操作（比如插入新节点），最后返回 dummyHead.next 即为结果链表的头节点。
   • carry 用于存储相加时的进位。
   • 使用 while 循环逐位相加 l1 和 l2，直到遍历完所有节点。

3. 进位处理：

   • 如果 carry > 0，意味着最后还有进位，需要在结果链表的尾部再加上一个节点。

4. 示例：

   • 在 main 方法中，创建了两个链表 l1 和 l2，分别表示数字 342 和 465。相加的结果为 807，对应的链表形式为 7 -> 0 -> 8。

时间复杂度和空间复杂度

• 时间复杂度：O(max(m, n))，其中 m 和 n 分别是两个链表的长度。我们需要遍历两个链表的所有节点。
• 空间复杂度：O(max(m, n))，用于存储结果链表的节点。

总结

这道题的关键在于链表的逐位相加和进位处理。通过使用虚拟头节点来简化链表操作，并且在遍历时考虑进位问题，我们可以高效地解决这个问题。

原文地址：https://blog.csdn.net/m0_61840987/article/details/143001943

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！