LeetCode-链表思路进行两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将两个数相加起来，则会返回一个新的链表来表示它们的和。

例如：

输入：（2->4->3）+(5->6->4)

输出：7->0->8

原因：342+465=807

整体思路： 

将长度较短的链表在末尾补零使得两个链表长度相等，再一个一个元素对其相加（考虑到进位）：

1. 获取两个链表所对应的长度；
2. 在较短的链表末尾补零；
3. 对齐相加考虑进位；

#include <iostream>
using namespace std;
struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x):val(x),next(nullptr){}
};
class Solution {
public:
	ListNode* Add(ListNode* L1, ListNode* L2) {
		int len1 = 1;
		int len2 = 1;
		ListNode* p = L1;/*移动指针*/
		ListNode* q = L2;/*移动指针*/
		while (p->next!=nullptr) {
			++len1;
			p = p->next;/*L1的长度*/
		}
		while (q->next != nullptr) {
			++len2;
			q = q->next;/*L2的长度*/
		}
		if (len1 > len2)/*判断，L1比L2长*/ {
			for (int i = 0; i <= len1 - len2; ++i) {
				q->next = new ListNode(0);
				q = q->next;
			}
		}
		else/*否则，L2比L1长*/ {
			for (int i = 0; i <= len2 - len1; ++i) {
				p->next = new ListNode(0);
				p = p->next;
			}
		}
		p = L1;
		q = L2;
		bool count = false; /*记录进位*/
		ListNode* L3 = new ListNode(-1);/*存放结果的链表*/
		ListNode* T = L3;  /*L3移动指针*/
		int i = 0;/*记录结果*/
		while (p != nullptr && q != nullptr) {
			i = count + p->val + q->val;
			T->next = new ListNode(i % 10);
			count = i > 10 ? true : false;
			T = T->next;
			p = p->next;
			q = q->next;
		}
		if (count) /*若最后还有进位*/
		{
			T->next = new ListNode(1);
			T = T->next;
		}
		return L3->next;
	}
	ListNode* Create();
	void Print(ListNode* head);
/*private:
	ListNode* head, * tail;*/
};
ListNode* Solution::Create() {
	ListNode* p1,*head,*tail;
	head = new ListNode(0);
	if (head == nullptr) {
		head = new ListNode(0);
	}
	head->next = nullptr;
	tail = head;
	int k,t;
	cout << "请输入链表的长度：";
	cin >> k;
	cout << endl;
	cout << "请输入链表的数值：";
	while (k) {
		p1 = new ListNode(0);
		if (p1 == nullptr) {
			cout << "分配内存失败" << endl;
			return head;
		}
		cin >> t;
		p1->val = t;
		tail->next = p1;
		tail = p1;
		tail->next = nullptr;
		--k;
	}
	return head;
}
void Solution::Print(ListNode* head) {
	ListNode* p2 = head->next;
	if (p2 == nullptr) {
		cout << "链表是空的，分配内存失败" << endl;
	}
	while (p2 != nullptr) {
		cout << p2->val << " ";
		p2 = p2->next;
	}
}
int main()
{
	cout << "创建链表1：" << endl;
	Solution dp1;
	ListNode* d1=dp1.Create();
	dp1.Print(d1);
	cout <<'\n'<< endl;
	cout << "创建链表2：" << endl;
	Solution dp2;
	ListNode* d2=dp2.Create();
	dp2.Print(d2);
	cout << '\n' << endl;
	Solution dp;
	ListNode* d = dp.Add(d1, d2);
	dp.Print(d);
	return 0;
}