【LeetCode】Add Two Numbers

问题描述

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

给出两个数，计算它们的和，但这两个数逆序放在链表中，比如 342+465 转化成逆序链表即：(2 -> 4 -> 3) + (5 -> 6 -> 4)，得出的答案为：7 -> 0 -> 8

问题分析

解决两个数相加的问题，主要是解决进位。在这个场景中这个好解决，因为会依据链表向下的指针不断的next，每次保留两数相加的进位即可；但这个场景还有一个问题要解决，就是链表长度问题，因为有可能两个链表长度不同，所以要先将长度相同的部分进行相加，多余的链表部分之后再处理。

比如21+789，转化为链表相加即：

a: (1->2)
b: (9->8>->7)

相加过程即：

1+9 = 0

2+8 + 进位（1） = 1

好，到这儿相同长度部分就加完了，然后在处理第二个链表b剩余的7就行了。
7 + 进位（1）= 8

结果：（0->1->8）

代码

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(l1 == NULL || l2 == NULL){
        	return NULL;
        }
        int t = l1->val+l2->val;
		int carry = t/10; // 进位 
        ListNode* r = new ListNode(t%10);
        ListNode* head = r;
        l1 = l1->next;
		l2 = l2->next;
        while(l1!=NULL&&l2!=NULL) {
        	t = l1->val + l2->val + carry;
        	carry = t/10;
        	r->next= new ListNode(t%10);
        	l1 = l1->next;
			l2 = l2->next;
			r = r->next;        	
        }
        ListNode* rest = 0;
		if(l1!=NULL) rest = l1;
		if(l2!=NULL) rest = l2;
        while(rest!=NULL) {
        	t = rest->val + carry;
        	carry = t/10;
        	r->next= new ListNode(t%10);
        	rest = rest->next;
        	r = r->next;
        }
        if(carry != 0) {
        	r->next= new ListNode(carry);
        }
        return head;
    }
};

测试

int main(){
	ListNode* l1;
	ListNode* l2;
	ListNode a1[]={
		ListNode(1),ListNode(8)
	};
	ListNode a2[]={
		ListNode(5),ListNode(4),ListNode(9)
	};
	l1 = &a1[0];
	l2 = &a2[0];
	ListNode* t1 = l1;
	ListNode* t2 = l2;
	for(int i=1;i<2;i++) {
		t1->next = &(a1[i]);
		t1 = t1->next;
	}
	for(int i=1;i<3;i++) {
		t2->next = &(a2[i]);
		t2 = t2->next;
	}
	
	Solution s;
	ListNode* r = s.addTwoNumbers(l1,l2);
	while(r!=NULL) {
		cout<<r->val<<" ";
		r = r->next;
	}
}