CC150 2.5

2_5.cpp

/* CC150 2.5
 * You have two numbers represented by a linked list, where each node contains a single digit.
 * The digits are stored in reverse order, such that the Ts digit is at the head of the list.
 * Write a function that adds the two numbers and returns the sum as a linked list.
 * EXAMPLE
 * Input:(7-> 1 -> 6) + (5 -> 9 -> 2).That is,617 + 295.
 * Output: 2 -> 1 -> 9.That is, 912.
 * FOLLOW UP
 * Suppose the digits are stored in forward order. Repeat the above problem. EXAMPLE
 * Input:(6 -> 1 -> 7) + (2 -> 9 -> 5).That is,617 + 295.
 * Output: 9 -> 1 -> 2.That is, 912.
 */

#include <iostream>
#include <sstream>
#include <string>
#include <list>

using namespace std;

list<int> listAddRvs(list<int> lst1, list<int> lst2)
{
	auto k = lst1.size() - lst2.size(); // append zeros to shorter list so that two lists have same length
	if (k > 0) {
		for (; k > 0; --k) lst2.push_back(0);
	}
	else {
		for (; k < 0; ++k) lst1.push_back(0);
	}
	list<int> sum;
	int carry = 0; // carry bit
	for (auto beg1 = lst1.cbegin(), beg2 = lst2.cbegin();
		beg1 != lst1.cend() && beg2 != lst2.cend(); ++beg1, ++beg2) {
		sum.push_back((*beg1 + *beg2 + carry) % 10);
		carry = (*beg1 + *beg2 + carry) / 10; // update carry bit
	}
	if (carry)
		sum.push_back(carry);
	return sum;
}

list<int> listAddFwd(list<int> lst1, list<int> lst2) // reverse, add, reverse
{
	lst1.reverse();
	lst2.reverse();
	list<int> sum = listAddRvs(lst1, lst2);
	sum.reverse();
	return sum;
}

int main()
{
	string data1, data2;
	cin >> data1 >> data2; // input numbers to be added
	list<int> lst1, lst2;
	int digit;
	istringstream din; // use string stream to read data into linked lists
	din.str(data1);
	while (din >> digit)
		lst1.push_back(digit);
	din.clear();
	din.str(data2);
	while (din >> digit)
		lst2.push_back(digit);
	list<int> sum = listAddFwd(lst1, lst2); // perform addition
	cout << "Forward add:" << endl;
	for (auto i : lst1) cout << i;
	cout << " + ";
	for (auto i : lst2) cout << i;
	cout << " = ";
	for (auto i : sum) cout << i;
	cout << endl;
	return 0;
}

1. Reverse the linked list is really a good way to solve this problem.