Leetcode - 两数之和

问题

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

思路

1. 先将两数相加，再提取各位数字组成新链表。
   优点：代码简单
   缺点：无法用于大数计算

2. 边遍历边相加，同时构建链表节点。需要考虑进位问题。

代码

C++

bool flag = false;
ListNode* L3 = L2;
ListNode* cur=nullptr;
unsigned short val = 0;
while (L2 || L1)
{
	if (L2)
	{
		cur = L2;		//保存当前位置
		val = cur->val + flag;
		L2 = L2->next;
	}
	else
	{
		cur->next = L1;	//L2比L1短，直接链接到L1
		cur = L1;
		val = flag;
	}
		
	if (L1)
	{
		val += L1->val;
		L1 = L1->next;
	}

	cur->val = val % 10;
	(val > 9) ? flag = 1 : flag = 0;
}

if (L1 == 0 && L2 == 0 && flag == 1)
	cur->next = new ListNode(1);
return L3;

CSharp

int flag = 0;
int val = 0;
ListNode L3=L2;
ListNode cur=new ListNode(0);
while( L2!=null|| L1!=null)
{
	if(L2!=null)
	{
		cur = L2;
		val = cur.val+flag;
		L2 = L2.next;
	}
	else
	{
		cur.next = L1;
		cur = L1;
		val = flag;
	}

	if(L1!=null)
	{
		val += L1.val;
		L1 = L1.next;
	}
	cur.val = val % 10;
	flag = val > 9 ? 1 : 0;
}
if (L1 == null && L2 == null && flag == 1)
	cur.next = new ListNode(1);
return L3;

考查点：单链表、大数计算