算法 2. 两数相加

LeetCode https://leetcode.cn/problems/add-two-numbers/

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

思路

遍历计算每一位, 计算的同事需要考虑到进位的问题
遍历计算结束后, 如果有进位, 需要在返回的链表添加一个节点储存1
使用多个指针, 一个指向头节点, 一个指向当前节点

代码

#include <stdio.h>
#include <ctime>
#include <random>
struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(NULL) {}
	ListNode(int x) : val(x), next(NULL) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		auto a = l1;
		auto b = l2;
		ListNode * result = new ListNode(0);
		ListNode * head = result;
		int carry = 0;
		while (a || b || carry) {
			auto sum = 0;
			if (a) {
				sum += a->val;
				a = a->next;
			}
			if (b) {
				sum += b->val;
				b = b->next;
			}
			sum += carry;
			carry = sum / 10;
			result->val = sum % 10;
			if (a || b || carry) {
				result->next = new ListNode(0);
				result = result->next;
			}
		}
		return head;
	}
};