【力扣 2】两数相加 C++题解(链表+模拟+数学)

发布时间:2024年01月24日

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

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

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

示例 1:

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

输入:l1 = [0], l2 = [0]
输出:[0]
示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

提示:

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


思路

模拟两数相加的过程,从低位到高位逐位相加,并处理进位。

首先创建一个新的链表l3,用于存储结果,p3是用于遍历新链表的指针。

addTwoNumbers函数中,首先创建两个指针p1p2,分别指向两个输入链表的头部。然后开始一个循环,每次循环都处理一对对应的节点,即p1p2所指向的节点。

在循环中,首先确保p3的下一个节点存在,如果不存在则创建一个新节点。然后计算p1p2的值以及p3的值的和,这里p3的值可能是上一轮循环的进位。然后,将和的个位数存入p3所指向的节点,将和的十位数(即进位)存入p3的下一个节点。最后,将p1p2p3都向后移动一位,继续下一轮循环。

p1p2中的任何一个到达链表尾部时,循环结束。这时,可能还有一个链表没有遍历完,所以需要调用move函数,将剩余的节点也加入到新链表中。move函数的操作和主循环中的操作类似,只是每次只处理一个节点。

最后,将新链表的头部向后移动一位,跳过初始的空节点,然后返回新链表的头部,即得到两数相加的结果。


AC代码

/*
 * @lc app=leetcode.cn id=2 lang=cpp
 *
 * [2] 两数相加
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
	ListNode* l3 = new ListNode();
	ListNode* p3 = l3;

   public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode* p1 = l1;
		ListNode* p2 = l2;
		while (p1 != nullptr && p2 != nullptr) {
			if (p3->next == nullptr) {
				p3->next = new ListNode();
			}
			p3 = p3->next;
			int sum = p1->val + p2->val + p3->val;
			int s = sum % 10;
			int c = sum / 10;
			p3->val = s;
			if (c) {
				p3->next = new ListNode(c);
			}
			p1 = p1->next;
			p2 = p2->next;
		}
		move(p1);
		move(p2);
		l3 = l3->next;
		return l3;
	}

	void move(ListNode* p) {
		while (p != nullptr) {
			if (p3->next == nullptr) {
				p3->next = new ListNode();
			}
			p3 = p3->next;
			int sum = p->val + p3->val;
			int s = sum % 10;
			int c = sum / 10;
			p3->val = s;
			if (c) {
				p3->next = new ListNode(c);
			}
			p = p->next;
		}
	}
};
// @lc code=end

文章来源:https://blog.csdn.net/qq_34988204/article/details/135797757
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。