add two linked list as integer

Question:
You have two numbers represented by a linked list, where each node contains a single digit. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE:
input: (3 -> 1 -> 5), (5 -> 9 -> 2)
output: 9 -> 0 -> 7
Analyze:
use two stacks to store the numbers in the list, and then the last number of the lists will be on the top of the stacks, we pop the stack and add the numbers, and save the result into the linked list.
Code:
public static LinkedList addList(Node h1, Node h2) {
	//save the numbers in the list to stacks
	Stack<Node> s1 = new Stack<Node>();
	Stack<Node> s2 = new Stack<Node>();
	
	while(h1 != null) {
		s1.push(h1);
		h1 = h1.next;
	}
	while(h2 != null) {
		s2.push(h2);
		h2 = h2.next;
	}
	//LinkedList saves the result
	LinkedList list = new LinkedList();
	
	int sum = 0;
	int carry = 0;
	
	while(!s1.empty() && !s1.empty()) {
		sum = s1.pop().data + s2.pop().data + carry;
		carry = sum / 10;
		sum = sum % 10;
		list.addFirst(sum);
	}
	
	while(!s1.empty()) {
		sum = s1.pop().data + carry;
		carry = sum / 10;
		sum = sum % 10;
		list.addFirst(sum);
	}
	
	while(!s2.empty()) {
		sum = s1.pop().data + carry;
		carry = sum / 10;
		sum = sum % 10;
		list.addFirst(sum);
	}
	// don't forget the carry
	if (carry != 0) list.addFirst(carry);
	
	return list;
}
http://blog.csdn.net/beiyeqing teng

좋은 웹페이지 즐겨찾기