Home  >  Article  >  Database  >  CCI 2.5 链表整数求和

CCI 2.5 链表整数求和

WBOY
WBOYOriginal
2016-06-07 15:43:041211browse

给定两个用链表表示的整数,每一个节点包含一个数位。这些数位是反向存放的,也就是个位排在链表首部。编写函数对这两个整数求和,并用链表形式返回结果。 示例 输入:(7-1-6) (5-9-2), 即 617 295. 输出:2-1-9, 即912. 进阶 假设这些数位是正向存放的,请

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

示例

输入:(7->1->6) + (5->9->2), 即 617 + 295.

输出:2->1->9, 即912.

进阶

假设这些数位是正向存放的,请再做一遍。

示例

输入:(6->1->7) + (2->9->5), 即617 + 295.

输出:9->1->2, 即912.

**进阶的解法告诉我们,涉及单链表逆序的问题,可以借助栈来解决。

package test;

import java.util.Stack;

public class AddLinkedInt {
	
	//两个整数反向存放
	//即,个位排在链表的首部
	public Node addLinkedInt(Node l1, Node l2){
		
		Node newHead = new Node(0);
		Node tail = newHead;
		int carry = 0;
		Node p1 = l1, p2 = l2;
		while(p1!=null || p2!=null){
			int val1 = (p1==null)? 0 : p1.val;
			int val2 = (p2==null)? 0 : p2.val;
			int val = (val1+val2+carry)%10;
			carry = (val1+val2+carry)/10;
			tail.next = new Node(val);
			tail = tail.next;
		}
		if(carry != 0)
			tail.next = new Node(carry);
		return newHead.next;
	}
	
	//两个整数正向存放
	//即,个位排在链表的末尾
	public Node addLinkedInt(Node l1, Node l2){
		//这里要借助栈来处理
		Stack<integer> st1 = new Stack<integer>();
		Stack<integer> st2 = new Stack<integer>();
		Node p1=l1, p2=l2;
		//将两链表的数据分别压入栈中
		while(p1 != null){
			st1.push(p1.val);
			p1 = p1.next;
		}
		while(p2 != null){
			st2.push(p2.val);
			p2 = p2.next;
		}
		//将结果相加入栈
		Stack<integer> res = new Stack<integer>();
		int carry=0;
		while( !st1.empty() || !st2.empty()){
			int val1 = st1.empty() ? 0 : st1.pop();
			int val2 = st2.empty() ? 0 : st2.pop();
			res.push((val1+val2+carry)%10);
			carry = (val1+val2+carry)/10;
		}
		if(carry != 0)//注意进位的处理
			res.push(carry);
		Node newHead = new Node(0);
		Node tail = newHead;
		while(!res.empty()){
			tail.next = new Node(res.pop());
			tail = tail.next;
		}
		return newHead.next;	
	}
}
</integer></integer></integer></integer></integer></integer>


Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn