题目描述： 给定两个单链表，链表的每个节点代表一位数，计算两个数的和。例如： 输入链表（3->1->5）和链表（5->9->2），输出：8->0->8，即513+295=808，注意个位数在链表头 。
方法一：整数相加法 分别遍历两个链表，求出两个链表所代表的整数的值，然后把这两个整数进行相加，最后把它们的和用链表的形式表示出来。这种方法的优点是计算简单，但是有个非常大的 缺点： 当链表所代表的数很大时（超出了long int的表示范围，就无法使用这种方法了）。
方法二：链表相加法 对链表中的节点直接进行相加操作，把相加的和存储到新的链表中对应的节点中。注意点：
任何情况都要考虑是否有进位两个链表长度不同怎么处理当计算完成后还有进位时，此进位只能是1，且要增加新的节点 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /** *方法功能：对两个带头节点的单链表所代表的数相加 *输入参数：h1：第一个链表头节点；h2：第二个链表头节点 *返回值：相加后链表的头节点 */ class Solution { public static ListNode add(ListNode h1,ListNode h2){ //排除单个链表为空的情况 if (h1 == null || h1.next == null){ return h2; } if (h2 == null || h2.next == null){ return h1; } //准备工作 int c = 0; //记录进位 int sum = 0; //记录两节点相加的值 ListNode p1 = h1.next; //用来遍历第一个链表 ListNode p2 = h2.next; //用来遍历第二个链表 ListNode tmp = null; //指向新创建的存储相加和的节点 //新建链表 ListNode resultHead = new ListNode(); //相加后链表的头节点 ListNode p = resultHead; //指向新链表最后一个节点，因为该链表要连接新的节点 //两条链表同长度部分 while (p1 != null && p2 != null){ //相加前新建一个节点，用来存储两个节点相加的和 tmp = new ListNode(); tmp.next = null; //相加操作 sum = p1.val + p2.val + c; //切莫忘记加上进位 tmp.val = sum%10; //两节点相加和 c = sum/10; //进位 //把新节点连到新链表上 p.next = tmp; p = tmp; //p依然要指向新链表的最后一个节点 //向后移位，准备操作第二组节点 p1 = p1.next; p2 = p2.next; } //此时，两个链表可能长度不相同，分开考虑 //1.假设链表h1比链表h2长，此时只需要考虑链表h1剩余节点的值 if (p2 == null){ while (p1 != null){ tmp = new ListNode(); tmp.next = null; sum = p1.val + c; tmp.val = sum%10; c = sum/10; p.next = tmp; p = tmp; p1 = p1.next; } } //2.假设链表h2比链表h1长，此时只需要考虑链表h2剩余节点的值 if (p1 == null){ while (p2 != null){ tmp = new ListNode(); tmp.next = null; sum = p2.val + c; tmp.val = sum%10; c = sum/10; p.next = tmp; p = tmp; p2 = p2.next; } } //如果计算完成后还有进位，则增加新的节点 if (c == 1){ tmp = new ListNode(); tmp.next = null; tmp.val = 1; p.next = tmp; } return resultHead; } }