LinkLists 两个链表相加 @CareerCup

原文：

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 1’s 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: (3 -> 1 -> 5), (5 -> 9 -> 2)

Output: 8 -> 0 -> 8

译文：

你有两个由单链表表示的数。每个结点代表其中的一位数字。数字的存储是逆序的， 也就是说个位位于链表的表头。写一函数使这两个数相加并返回结果，结果也由链表表示。

例子：(3 -> 1 -> 5), (5 -> 9 -> 2)

输入：8 -> 0 -> 8

思路：递归

1） 如果整数在链表中是以倒置方式存放的，那么容易相加

2） 如果整数在链表中是以顺序方式存放的，那么要 1先分别计算两个链表长度 2 把短的链表短的部分补零，使得两链表长度相同 3 递归相加，返回值用一个WrapperNode，不光存放相加后的节点，而且存放carry值。 所以用到方法有：length，padList，addListsHelper，insertBefore

值得主义的情况有：1.链表为空。2.有进位。3.链表长度不一样。

package LinkLists;

import CtCILibrary.LinkedListNode;

public class S2_5 {

	// 当值以reverse order存放在链表时，递归
	// 如：         9->9->9
	// 			+ 1
	//          = 0->0->0->1
	public static LinkedListNode addListsReverse(LinkedListNode l1, LinkedListNode l2,
			int carry) {
		if (l1 == null && l2 == null && carry == 0) {
			return null;
		}

		// 新建当前结果节点
		LinkedListNode result = new LinkedListNode(carry, null, null);

		int value = carry;
		if (l1 != null) {
			value += l1.data;
		}
		if (l2 != null) {
			value += l2.data;
		}

		result.data = value % 10; // 设置当前结果节点值
		// 递归
		result.next = addListsReverse(l1 == null   null : l1.next, l2 == null   null
				: l2.next, value / 10);

		return result;
	}
	
	
	//===========================================
	// 当把值以顺序存放链表：
	// 如：         9->9->9
	// 		  	          + 1
	//     = 1->0->0->0
	public static LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2) {
		int len1 = length(l1);
		int len2 = length(l2);
		
		// 给较短的链表补零
		if(len1 < len2) {
			l1 = padList(l1, len2-len1);		// 9->9->9
		} else{
			l2 = padList(l2, len1-len2);		// 0->0->1
		}
		
//		System.out.println("pad1: " + l1.printForward());
//		System.out.println("pad2: " + l2.printForward());
		
		WrapperNode sum = addListsHelper(l1, l2);
		
		if(sum.carry == 0) {
			return sum.node;
		} else{		// 对于最后仍有进位的情况，如：999+1=1000
			LinkedListNode result = insertBefore(sum.node, sum.carry);
			return result;
		}
	}
	
	public static int length(LinkedListNode head) {
		if(head == null){
			return 0;
		} else{
			return 1 + length(head.next);
		}
	}
	
	// 递归，两个链表相加
	//     l1  l1.next
	// 9->9->9
	// 0->0->1
	//        ->0  head(carry:1)
	//      0->0 
	//    head(carry:1)
	public static WrapperNode addListsHelper(LinkedListNode l1, LinkedListNode l2) {
		if(l1 == null && l2 == null) {
			WrapperNode head = new WrapperNode();
			return head;
		}

		// 利用递归返回下一个节点之和以及carry，都封装在head里
		WrapperNode head = addListsHelper(l1.next, l2.next);
		int val = head.carry + l1.data + l2.data;		// 计算当前节点的和
		
		// 把当前节点插在旧的head之前，并保存新的carry值
		LinkedListNode newHead = insertBefore(head.node, val%10);
		return new WrapperNode(newHead, val/10);		// 返回新的wrapper，包含新头结点和carry
	}
	
	// 在head节点前面补上padding个零
	public static LinkedListNode padList(LinkedListNode head, int padding) {
		LinkedListNode cur = head;
		for(int i=0; i
  
		
   
		
	
   
 
   
	
   
 
    

     <script type="text/java script">BAIDU_CLB_fillSlot("771048");
    
 
   
	
   
 
    

     点击复制链接 与好友分享!
     回本站首页
    
 
    <script> 
		function copyToClipBoard(){ 
		var clipBoardContent=document.title + '\r\n' + document.location; 
		clipBoardContent+='\r\n'; 
		window.clipboardData.setData("Text",clipBoardContent); 
		alert("恭喜您！复制成功"); 
		} 
		 
    
 
      
     
 
      分享到： 
       
       
       
       
       
       
       
      更多 
     
 
     <script type="text/java script" id="bdshare_js" data="type=tools&uid=12732"> 
     <script type="text/java script" id="bdshell_js"> 
     <script type="text/java script">
var bds_config = {'snsKey':{'tsina':'2386826374','tqq':'5e544a8fdea646c5a5f3967871346eb8'}};
document.getElementById("bdshell_js").src = "http://bdimg.share.baidu.com/static/js/shell_v2.js cdnversion=" + Math.ceil(new Date()/3600000)