You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
給定兩個(gè)代表兩個(gè)非負(fù)數(shù)的鏈表，按數(shù)位逆置方式存儲(chǔ)（即123存儲(chǔ)為3→2→1→NULL），要求返回兩數(shù)之和的鏈表迄本。
思路：
【方法1】將兩個(gè)鏈表轉(zhuǎn)換為整數(shù)聘萨，相加后再轉(zhuǎn)換為鏈表返回，需要注意int型表示的范圍朦促，必要時(shí)需要使用long int或longlong犬钢；
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if(!l1 || !l2) return(!l1)?l2:l1;
long int n1=0,n2=0,n3=0,digit=0,count=1;
ListNode *p=l1;
while(p){
digit=p->val;
n1=n1+digit*count;
p=p->next;
count*=10;
}
p=l2;
count=1;
while(p){
digit=p->val;
n2=n2+digit*count;
p=p->next;
count*=10;
}
n3=n1+n2;
ListNode *res=new ListNode(n3%10);
n3/=10;
p=res;
for(;n3>0;n3/=10){
ListNode *tmp=new ListNode(n3%10);
p->next=tmp;
p=tmp;
}
p->next=nullptr;
return res;
}
};
【方法2】直接在鏈表上進(jìn)行處理，由于鏈表是逆序數(shù)位存儲(chǔ)思灰，相當(dāng)于整數(shù)右對(duì)齊加法玷犹，相加時(shí)注意進(jìn)位以及兩數(shù)位數(shù)不一致的情況。
兩種方法相比較而言方法1較為簡(jiǎn)單洒疚，但處理位數(shù)受限歹颓，耗時(shí)較長(zhǎng)。
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = NULL, *prev = NULL;
int carry = 0;
while (l1 || l2) {
int v1 = l1? l1->val: 0;
int v2 = l2? l2->val: 0;
int tmp = v1 + v2 + carry;
carry = tmp / 10;
int val = tmp % 10;
ListNode* cur = new ListNode(val);
if (!head) head = cur;
if (prev) prev->next = cur;
prev = cur;
l1 = l1? l1->next: NULL;
l2 = l2? l2->next: NULL;
}
if (carry > 0) {
ListNode* l = new ListNode(carry);
prev->next = l;
}
return head;
}
