现在位置: 首页 / 学习 / leetcode / 正文

LeetCode第二题：两数相加

  • admin
  • 学习
  • 2023-09-06
  • 78热度
  • 0评论

题目来源：LeetCode第二题

1.题目描述

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

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

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

示例1：

LeetCode第二题：两数相加插图

输入：l1 = [2,4,3], l2 = [5,6,4]

输出：[7,0,8]

解释：342 + 465 = 807

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

2.解题思路

解法一：模拟法

  • 描述：我们可以初始化一个链表来存储结果，并维护一个进位变量carry，遍历两个链表，直到两个都为null，如果其中一个链表提前结束，就把值视为0，计算两个节点与进位的和，并且更新进位，将和的个位存储在新链表中，最后如果还有进位就将进位值添加到新链表中。
  • 时间复杂度：O(max(m, n))。其中 m 和 n 分别是两个链表 l1 和 l2 的长度。在最坏的情况下，我们需要遍历两个链表的所有元素，因此时间复杂度取决于最长的链表。
  • 空间复杂度：O(1)。这是因为我们所使用的额外空间是常数的，即不依赖于输入大小的变量和进位标志。输出的新链表并不算作额外的空间使用，因此应视为常数空间 O(1)。
  • 参考代码：

Java版：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 创建虚拟头节点
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        // 记录进位
        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 dummyHead.next;
    }

C++版:

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		// 创建一个虚拟头节点
		ListNode* dummyHead = new ListNode();
		ListNode* current = dummyHead;
		// 用于记录进位
		int carry = 0;
		// 当两个链表中至少有一个还未遍历完时
		while (l1 != nullptr || l2 != nullptr)
		{
			// 获取当前节点的值，如果链表已结束则值为0
			int x = (l1 != nullptr) ? l1->val : 0;
			int y = (l2 != nullptr) ? l2->val : 0;
			// 计算当前两节点的和以及进位
			int sum = x + y + carry;
			carry = sum / 10;
			// 将和的个位数作为新的节点加到结果链表中
			current->next = new ListNode(sum % 10);

			// 都移动到下一个节点不为空的话
			current = current->next;
			if (l1 != nullptr)
				l1 = l1->next;
			if (l2 != nullptr)
				l2 = l2->next;
		}
		// 都加完之后如果还有进位的话，存在新的节点中
		if (carry > 0)
		{
			current->next = new ListNode(carry);
		}
		//使用 new 创建的链表节点在不再需要时被 delete 删除，以避免内存泄漏。
		ListNode* result = dummyHead->next;
		delete dummyHead;
		return result;
	}
};

C版:

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	// 初始化一个虚拟头节点
	struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
	dummyHead->val = 0;
	dummyHead->next = NULL;

	struct ListNode* current = dummyHead; // 当前操作的节点，初始化为虚拟头节点
	int carry = 0; // 初始化进位为0

	// 当l1和l2中至少有一个还未遍历完时
	while (l1 != NULL || l2 != NULL) {
		// 如果l1还未遍历完，则取l1当前节点的值，否则为0
		int x = (l1 != NULL) ? l1->val : 0;
		// 如果l2还未遍历完，则取l2当前节点的值，否则为0
		int y = (l2 != NULL) ? l2->val : 0;

		// 计算当前两节点的和以及进位
		int sum = x + y + carry;
		carry = sum / 10; // 计算进位

		// 创建新节点并添加到结果链表
		current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
		current->next->val = sum % 10; // 取sum的个位数
		current->next->next = NULL;
		current = current->next; // 移动current指针到新节点

		// 如果l1和l2还未遍历完，则移动到下一个节点
		if (l1 != NULL) l1 = l1->next;
		if (l2 != NULL) l2 = l2->next;
	}

	// 遍历完l1和l2后，如果还有进位，则创建一个新节点存储进位
	if (carry > 0) {
		current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
		current->next->val = carry;
		current->next->next = NULL;
	}

	// 使用虚拟头节点可以简化代码逻辑
	struct ListNode* result = dummyHead->next; // 结果链表的真实头节点
	free(dummyHead); // 释放虚拟头节点的内存
	return result;
}

解法二：递归法

  • 描述：对于这个问题，我们可以先只考虑两个链表的第一个节点的加法运算，然后递归的处理剩下的部分。首先确定递归什么时候结束，本题递归结束条件是两个链表都为空并且没有进位。取出链表当前位置的值（为空就当作0），和carry值进行相加得到当前位置的总和。计算新的进位值（总和/10）和当前位置的结果值（总和%10）。新建节点存储当前位置的值，并且将两个链表的下一个节点和新的进位值放入递归函数中。递归出的结果作为新建节点的next。返回节点。
  • 时间复杂度：O(max(m, n))。其中 m 和 n 分别是两个链表 l1 和 l2 的长度。在最坏的情况下，我们需要遍历两个链表的所有元素，因此时间复杂度取决于最长的链表。
  • 空间复杂度：O(max(m, n))。虽然我们返回的链表长度是 O(max(m, n))，但递归方法的调用栈深度也可能达到 O(max(m, n))，特别是在处理长链表时。因此，递归解的总体空间复杂度也是 O(max(m, n))。
  • 参考代码：

java版:

class Solution {
     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return addWithCarry(l1, l2, 0);
    }

    private ListNode addWithCarry(ListNode l1, ListNode l2, int carry) {
        // 递归的停止条件
        if (l1 == null && l2 == null && carry == 0) {
            return null;
        }
        int sum = carry;
        // 如果l1没遍历完，加上l1当前的节点值
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        // 如果l2没遍历完，加上l2当前的节点值
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        // 建新节点存储sum的个位数
        ListNode current = new ListNode(sum % 10);
        // 递归的处理下一位
        current.next = addWithCarry(l1, l2, sum / 10);
        // 返回这一层的节点
        return current;
    }
}

C++版:

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		return addWithCarry(l1, l2, 0);
	}
private:
	ListNode* addWithCarry(ListNode* l1, ListNode* l2, int carry)
	{
		//递归结束条件
		if (!l1 && !l2 && carry == 0)
		{
			return nullptr;
		}
		int sum = carry;

		// 如果l1还未遍历完，加上l1当前节点的值
		if (l1)
		{
			sum += l1->val;
			l1 = l1->next;
		}

		// 如果l2还未遍历完，加上l2当前节点的值
		if (l2)
		{
			sum += l2->val;
			l2 = l2->next;
		}
		// 建新节点存储sum的个位数
		ListNode* current = new ListNode(sum % 10);
		// 递归的处理下一位
		current->next = addWithCarry(l1, l2, sum / 10);
		// 返回这一层的节点
		return current;
	}
};

C版:

struct ListNode* addWithCarry(struct ListNode* l1, struct ListNode* l2, int carry) {
	// 当两个链表都为空且没有进位时返回NULL
	if (!l1 && !l2 && carry == 0) {
		return NULL;
	}

	int sum = carry;

	// 如果l1还未遍历完，加上l1当前节点的值
	if (l1) {
		sum += l1->val;
		l1 = l1->next;
	}

	// 如果l2还未遍历完，加上l2当前节点的值
	if (l2) {
		sum += l2->val;
		l2 = l2->next;
	}

	// 创建新节点存储sum的个位数，并递归地处理下一个位置
	struct ListNode* current = (struct ListNode*)malloc(sizeof(struct ListNode));
	current->val = sum % 10;
	current->next = addWithCarry(l1, l2, sum / 10);

	return current;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
	return addWithCarry(l1, l2, 0);
}