【力扣 445】两数相加 II C++题解（链表+模拟+数学+头插法）

本文介绍: 给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。示例1：输入：l1 = [7,2,4,3], l2 = [5,6,4]输出：[7,8,0,7]示例2：输入：l1 = [2,4,3], l2 = [5,6,4]输出：[8,0,7]示例3：输入：l1 = [0], l2 = [0]输出：[0]提示：链表的长度范围为 [1, 100]

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]
示例3：

输入：l1 = [0], l2 = [0]
输出：[0]

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

// @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* rl1 = reverse(l1);
		ListNode* rl2 = reverse(l2);
		ListNode* p1 = rl1;
		ListNode* p2 = rl2;
		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;
		ListNode* rl3 = reverse(l3);
		return rl3;
	}

	ListNode* reverse(ListNode* l) {
		ListNode* rl = new ListNode();
		ListNode* p = l;
		ListNode* rp;
		while (p != nullptr) {
			rp = new ListNode(p->val);
			rp->next = rl->next;
			rl->next = rp;
			p = p->next;
		}
		rl = rl->next;
		return rl;
	}

	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