LeetCode 2. 两数相加

题目描述

给你两个非空的链表，表示两个非负整数。它们每位数字都是按逆序的方式存储的，也就是最左边的数字是最低位的数字。请你将这两个数相加，并以相同逆序的方式返回一个新的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

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

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 链表的长度在范围 [1, 100] 内

Java 实现解法

方法：模拟加法过程

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
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;
    }
}

解题思路

• 模拟加法过程：从头节点开始，遍历两个链表，对应节点的值相加，并考虑进位。
  • 初始化一个虚拟头节点 dummyHead，用于简化边界情况处理。
  • 初始化两个指针 p 和 q 分别指向两个链表的头节点，以及一个指针 current 指向 dummyHead。
  • 初始化一个变量 carry 用于存储进位。
  • 在循环中，计算当前位的和 sum，并更新进位 carry。
  • 创建一个新的节点 current.next 存储当前位的和（不包括进位）。
  • 更新 p 和 q 指针到下一个节点，并将 current 指针前移。
  • 如果最后还有进位，创建一个新的节点存储这个进位。

这种方法的时间复杂度是 O(max(m, n))，其中 m 和 n 分别是两个链表的长度。空间复杂度是 O(max(m, n))，因为我们需要创建一个与较长链表长度相当的新链表来存储结果。这种方法直接模拟了两个数相加的过程，简单且高效。

注：来源leetcode网站