[数据结构与算法]LeetCode笔记-02-两数相加

问题的本质就是两个单链表的合并；
注意点是：
1.在一条链表结束时，是否还需要进位，如果需要进位，就需要将另外一条单链表循序加进位；
2.在两条链表遍历结束时，是否还有进位，如果有就要在单链表的末尾增加节点；

代码

新单链表

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 {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		if (l1 == nullptr && l2 == nullptr) {
			return nullptr;
		}
		ListNode* result = new ListNode;
		ListNode* pCurrent = result;
		ListNode* pPre = nullptr;
		int add = 0;
		while (l1 != nullptr && l2 != nullptr) {
			int sum = l1->val + l2->val + add;
			pCurrent->val = sum % 10;
			add = sum / 10;
			l1 = l1->next;
			l2 = l2->next;
			pCurrent->next = new ListNode;
			pPre = pCurrent;
			pCurrent = pCurrent->next;
		}

		while (l1 != nullptr)
		{
			int sum = l1->val + add;
			pCurrent->val = sum % 10;
			add = sum / 10;
			l1 = l1->next;
			pCurrent->next = new ListNode;
			pPre = pCurrent;
			pCurrent = pCurrent->next;
		}
		while (l2 != nullptr)
		{
			int sum = l2->val + add;
			pCurrent->val = sum % 10;
			add = sum / 10;
			l2 = l2->next;
			pCurrent->next = new ListNode;
			pPre = pCurrent;
			pCurrent = pCurrent->next;
		}

		if (add != 0)
		{
			pCurrent->val = add;
		}
		else
		{
			delete pPre->next;
			pPre->next = nullptr;
		}
		return result;
	}
};

使用现有单链表

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		if (l1 == nullptr && l2 == nullptr) {
			return nullptr;
		}
		ListNode* result = l1;
		ListNode* pre = nullptr;
		int add = 0;
		while (l1 != nullptr && l2 != nullptr){
			int sum = l1->val + l2->val + add;
			l1->val = sum % 10;
			add = sum / 10;
			pre = l1;
			l1 = l1->next;
			l2 = l2->next;
		}
		if (l2 != nullptr){
			pre->next = l2;
			while (l2 != nullptr&&add != 0) {
				int sum = l2->val + add;
				l2->val = sum % 10;
				add = sum / 10;
				pre = l2;
				l2 = l2->next;
			}			
		}
		else {
			while (l1 != nullptr && add != 0) {
				int sum = l1->val + add;
				l1->val = sum % 10;
				add = sum / 10;
				pre = l1;
				l1 = l1->next;
			}
		}
		if (add != 0) {
			pre->next = new ListNode(add);
		}
		return result;
    }
};

消灭除法

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		if (l1 == nullptr && l2 == nullptr) {
			return nullptr;
		}
		ListNode* result = l1;
		ListNode* pre = nullptr;
		int add = 0;
		while (l1 != nullptr && l2 != nullptr){
			int sum = l1->val + l2->val + add;
			l1->val = sum % 10;
			add = sum > 9;
			pre = l1;
			l1 = l1->next;
			l2 = l2->next;
		}
		if (l2 != nullptr){
			pre->next = l2;
			while (l2 != nullptr&&add != 0) {
				int sum = l2->val + add;
				l2->val = sum % 10;
				add = sum > 9;
				pre = l2;
				l2 = l2->next;
			}			
		}
		else {
			while (l1 != nullptr && add != 0) {
				int sum = l1->val + add;
				l1->val = sum % 10;
				add = sum > 9;
				pre = l1;
				l1 = l1->next;
			}
		}
		if (add != 0) {
			pre->next = new ListNode(add);
		}
		return result;
    }
};