博客

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
结果：342 + 465 = 807

解法：

package test001;

/**
 * @author zhenqingshi
 *
 * 2018年7月7日
 */

//ListNode链表类定义
class ListNode{
    int val;
    ListNode nextNode;
    ListNode(int val){
        this.val=val;
        this.nextNode=null;
    }
}
public class Listnode_sum {
    //两逆序存储的链表相加
     public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	    ListNode dummyHead = new ListNode(0);
	    ListNode p = l1, q = l2, curr = dummyHead;
	    int carry = 0;
	    while (p != null || q != null) {
	        int x = (p != null) ? p.val : 0;//将$x$设为节点$p$的值,如果$p$已经到达l1的末尾，则将其值设置为0。
	        int y = (q != null) ? q.val : 0;
	        int sum = carry + x + y;//得到节点的和
	        carry = sum / 10;//存在进位则置1
	        curr.nextNode = new ListNode(sum % 10);//将sum的个位数添加至下一节点
	        curr = curr.nextNode;//curr后移至下一节点，同c中的curr=curr->next
	        if (p != null) 
	        	p = p.nextNode;
	        if (q != null) 
	        	q = q.nextNode;
	    }
	  
	    if (carry > 0) {
	        curr.nextNode = new ListNode(carry);   
	    }//如果最后存在进位，则追加节点1

        /*dummyHead=dummyHead.nextNode; 
        printList(dummyHead);
        return dummyHead; */

        return dummyHead.nextNode;  
	}
	// 遍历输出链表
	 public static void printList(ListNode head){
		ListNode temp = head;
	        while(temp != null){
	            System.out.print(temp.val+" ");
	            temp = temp.nextNode;
	        }
	        System.out.println();
	    }
	 //初始化链表
	 public static ListNode buildListNode(int[] input){
	        ListNode first = null,last = null,newNode;
	        if(input.length>0){
	            for(int i=0;i<input.length;i++){
	                newNode=new ListNode(input[i]);
	                newNode.nextNode=null;
	                if(first==null){
	                    first=newNode;
	                    last=newNode;
	                }
	                else{
	                    last.nextNode=newNode;
	                    last=newNode;
	                }
	            }
	        }
	        return first;
	    }
	 
	 //主方法
	 public static void main(String [] args){
	      int[] input=new int[]{2,4,3};
	      ListNode listNode1=buildListNode(input);
	      int[] input2=new int[]{5,6,4};
	      ListNode listNode2=buildListNode(input2);
	      ListNode listNode3=addTwoNumbers(listNode1,listNode2);
	      printList(listNode3);
	   }
}

题目转自LeetCode，解法参考其解决方案及网络资源。