【Java】对两个用链表表示的整数求和

给定两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。

	public LinkedList addLists(LinkedList l1, LinkedList l2, int carry){
		if (null == l1 && null == l2 && 0 == carry) return null;
		LinkedList result = new LinkedList();
		int value = carry;
		if (l1 != null) value += l1.data;
		if (l2 != null) value += l2.data;
		result.data = value % 10;
		LinkedList more = addLists(null == l1? null : l1.next, null == l2? null : l2.next, value > 10? 1 : 0);
		result.setNext(more);
		return result;
		
	}

注意要避开空指针一场，如果两个数位数不同，需要在较小数的末尾补零进行相加

public class PartialSum {
	public LinkedList sum = null;
	public int carry = 0;
}

LlinkedList addLists(LinkedList l1, LinkedList l2) {
	int len1 = length(l1);
	int len2 = length(l2);
	
	if(len1 < len2) {
		l1 = padList(l1, len2 - len1);
	}
	else {
		l2 = padList(l2, len1 - len2);
	}
	
	PartialSum sum = addListsHelper(l1, l2);
	if (sum.carry == 0) {
		return sum.sum;
	}
	else {
		LinkedList result = interBefore(sum.sum, sum.carry);
		return result;
	}
}

PartialSum addListsHelper(LinkedList l1, LinkedList l2) {
	if (null == l1 && null == l2) {
		PartialSum sum = new PartialSum();
		return sum;
	}
	
	PartialSum sum = addListHelper(l1.next, l2.next);
	int val = sum.carry + l1.data + l2.data;
	LinkedList full_result = insetBefore(sum.sum, val%10);
	sum.sum = full_result;
	sum.carry = val / 10;
	return sum;
}

LinkedList padList(LinkedList l, ind padding) {
	LinkedList head = l;
	for (int i = 0; i< padding; i++) {
		LinkedList n = new LinkedList(0, null, null);
		head.pre = n;
		n.next = head;
		head = n;
	}
	return head;
}

LinkedList insetBefore(LinkedList list, int data) {
	LinkedList node = new LinkedList(data, null, null);
	if(list != null) {
		list.prev = node;
		node.next = list;
	}
	return node;
}

int length(LinkedList l) {
	int count = 0;
	LinkedList p = l;
	if (null == l) return 0;
	while (p != null) {
		count++;
		p = p.next;
	}
	return count;
}

最后

以上就是笨笨手套为你收集整理的【Java】对两个用链表表示的整数求和的全部内容，希望文章能够帮你解决【Java】对两个用链表表示的整数求和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。