首页 > ACM题库 > LeetCode > leetCode-Add Two Numbers[题解]
2014
03-20

leetCode-Add Two Numbers[题解]

题目Add Two Numbers 面试频率:难度:3   (1-5)

http://oj.leetcode.com/problems/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

大意:给两个链表代表两个反向存储的数字,返回他们的和,用链表表示。

数据结构的基础题,链表模拟。完整代码如下:

#include <iostream>
using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) :
		val(x), next(NULL) {
	}
};

class Solution {
public:
	ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
		ListNode * ans = NULL, *last = NULL;
		int up = 0;
		while (NULL != l1 && NULL != l2) {
			int tmp = l1->val + l2->val + up;
			up = tmp / 10;
			//第一个单独处理
			if (NULL == last) {
				ans = new ListNode(tmp % 10);
				last = ans;
			} else
				last = pushBack(last, tmp % 10);
			l1 = l1->next;
			l2 = l2->next;
		}
		while (NULL != l1) {
			int tmp = l1->val + up;
			last = pushBack(last, tmp % 10);
			up = tmp / 10;
			l1 = l1->next;
		}
		while (NULL != l2) {
			int tmp = l2->val + up;
			last = pushBack(last, tmp % 10);
			up = tmp / 10;
			l2 = l2->next;
		}
		if (0 != up) {
			ListNode * l = new ListNode(up);
			last->next = l;
		}
		return ans;
	}

	//在末尾添加值val,返回链表尾
	ListNode * pushBack(ListNode * last, int val) {
		ListNode * l = new ListNode(val);
		last->next = l;
		return l;
	}
};

//测试
int main() {
	ListNode * ln1 = new ListNode(9);
	ListNode * ln2 = new ListNode(9);
	ln1->next = ln2;
	//ListNode * ln3 = new ListNode(3);
	//ln2->next = ln3;
	ListNode * n1 = new ListNode(1);
	//	ListNode * n2 = new ListNode(6);
	//	n1->next = n2;
	//	ListNode * n3 = new ListNode(4);
	//	n2->next = n3;
	Solution s;
	ListNode * ans = s.addTwoNumbers(ln1, n1);
	while (NULL != ans) {
		cout << ans->val << " ";
		ans = ans->next;
	}
	return 0;
}

ACM之家原创,链接:http://www.acmerblog.com/leetcode-add-two-numbers-5227.html