Leetcode2

一、问题理解与分析

首先，让我们来理解这个问题：我们需要实现两个用链表表示的非负整数的加法。这里有几个关键点：

  1. 链表中的每个节点存储一个数字（0-9）
  2. 数字是按照逆序方式存储的（个位在前，十位在后，依此类推）
  3. 我们需要返回一个新的链表，表示这两个数的和

例如：

  • 链表 l1 = [2,4,3] 表示数字 342（因为是逆序）
  • 链表 l2 = [5,6,4] 表示数字 465
  • 它们的和是 807，所以结果链表应该是 [7,0,8]

在开始思考解决方案前，我需要理解链表的结构。通常，链表节点定义如下：

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

二、初步思路与实现

这个问题实际上模拟了我们在纸上做加法的过程，只是数字是以链表形式存储的。

初步思路：

  1. 同时遍历两个链表
  2. 对每一位进行相加，并考虑进位
  3. 创建新的节点来存储每一位的和
  4. 如果最后还有进位，需要增加一个新节点

让我们开始实现：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // 创建一个哑节点作为结果链表的头部
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    // 进位值，初始为0
    int carry = 0;
    
    // 遍历两个链表
    while (l1 != null || l2 != null) {
        // 获取当前位的值，如果链表已经结束则为0
        int x = (l1 != null) ? l1.val : 0;
        int y = (l2 != null) ? l2.val : 0;
        
        // 计算当前位的和，包括进位
        int sum = x + y + carry;
        
        // 更新进位值
        carry = sum / 10;
        
        // 创建新节点存储当前位的值
        current.next = new ListNode(sum % 10);
        current = current.next;
        
        // 移动到下一位
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    
    // 检查最终是否还有进位
    if (carry > 0) {
        current.next = new ListNode(carry);
    }
    
    return dummy.next;
}

让我们用示例1来手动模拟一下：

  • l1 = [2,4,3], l2 = [5,6,4]
  • 第一位：2 + 5 + 0(进位) = 7，进位 = 0，结果链表 = [7]
  • 第二位：4 + 6 + 0(进位) = 10，进位 = 1，结果链表 = [7,0]
  • 第三位：3 + 4 + 1(进位) = 8，进位 = 0，结果链表 = [7,0,8]

这符合预期结果 [7,0,8]，说明我们的算法初步是正确的。

三、边界情况分析与优化

现在让我们考虑一些边界情况：

  1. 两个链表长度不同：我们的算法已经考虑了这种情况，通过在短链表结束后使用0值来处理。

  2. 有进位到最高位：例如示例3，l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]，最终会有进位产生新的一位。我们的算法也处理了这种情况。

  3. 空链表：题目说明链表非空，所以不需要处理空链表的情况。

让我再仔细检查一下代码逻辑：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = 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 = x + y + carry;
        
        carry = sum / 10;
        current.next = new ListNode(sum % 10);
        current = current.next;
        
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    
    if (carry > 0) {
        current.next = new ListNode(carry);
    }
    
    return dummy.next;
}

这个实现已经很简洁和高效，时间复杂度是O(max(m,n))，空间复杂度是O(max(m,n))，其中m和n是两个链表的长度。

为了验证代码的正确性，让我们再手动检查一个例子，示例3：

  • l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

模拟过程：

  • 第1位：9 + 9 + 0(进位) = 18，进位 = 1，结果 = [8]
  • 第2位：9 + 9 + 1(进位) = 19，进位 = 1，结果 = [8,9]
  • 第3位：9 + 9 + 1(进位) = 19，进位 = 1，结果 = [8,9,9]
  • 第4位：9 + 9 + 1(进位) = 19，进位 = 1，结果 = [8,9,9,9]
  • 第5位：9 + 0 + 1(进位) = 10，进位 = 1，结果 = [8,9,9,9,0]
  • 第6位：9 + 0 + 1(进位) = 10，进位 = 1，结果 = [8,9,9,9,0,0]
  • 第7位：9 + 0 + 1(进位) = 10，进位 = 1，结果 = [8,9,9,9,0,0,0]
  • 最后还有进位1，添加一个节点，结果 = [8,9,9,9,0,0,0,1]

这与预期结果 [8,9,9,9,0,0,0,1] 一致，说明我们的算法正确处理了这种情况。

在思考优化的过程中，我发现上述算法已经非常高效，因为：

  1. 我们只需要遍历链表一次
  2. 我们使用了常数级别的额外空间（除了必须创建的结果链表）

因此，这个解决方案从时间和空间复杂度上来看都是最优的。

四、代码实现优化与详细注释

让我对代码做一些优化和改进，主要是提高可读性和健壮性：

/**
 * 将两个非空链表表示的非负整数相加
 * 每个链表节点包含一个数字，数字按照逆序方式存储
 * 返回相加结果，也是以逆序链表形式
 */
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // 创建一个哑节点作为结果链表的头部，简化操作
    ListNode dummyHead = new ListNode(0);
    ListNode current = dummyHead;
    
    // 表示进位的值，初始为0
    int carry = 0;
    
    // 当两个链表至少有一个非空，或者有进位时，继续循环
    while (l1 != null || l2 != null) {
        // 获取当前位的值，如果链表已结束则值为0
        int x = (l1 != null) ? l1.val : 0;
        int y = (l2 != null) ? l2.val : 0;
        
        // 计算当前位的和，包括上一位的进位
        int sum = carry + x + y;
        
        // 计算新的进位值（整除得到十位数）
        carry = sum / 10;
        
        // 创建新节点，值为当前位的结果（取余得到个位数）
        current.next = new ListNode(sum % 10);
        current = current.next;
        
        // 移动到下一个节点，如果链表已结束则保持为null
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    
    // 如果所有位都处理完后还有进位，添加一个新节点
    if (carry > 0) {
        current.next = new ListNode(carry);
    }
    
    // 返回哑节点的下一个节点，即结果链表的头节点
    return dummyHead.next;
}

在这个最终版本中，我添加了详细的注释来解释每一步的目的和逻辑，使代码更易于理解和维护。变量命名也更加清晰，例如使用dummyHead而不是简单的dummy，以便更好地表达其作用。

整体来看，这个算法:

  • 时间复杂度：O(max(m,n))，其中m和n是两个链表的长度
  • 空间复杂度：O(max(m,n))，用于存储结果链表

现在，让我提供完整的代码实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, current = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • LeetCode2 两数相加
    题目说明 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的...
    亖狼何需装羴阅读 114评论 0赞 0
  • Leetcode2:python实现
    给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你...
    荆楚狂人阅读 302评论 0赞 0
  • LeetCode2
    用链表表示整数，求其相加得到的结果。考察基本的链表操作。因为用的是Java刷题，所以要清楚Java的链表实现。Ja...
    千舟1900阅读 215评论 0赞 0
  • LeetCode2——Add Two Numbers
    题目 You are given two non-empty linked lists representing ...
    泽泽馥泽泽阅读 181评论 0赞 0
  • leetcode2
    给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 ...
    大写的空气阅读 149评论 0赞 0