LeetCode|leetcode 2. 两数相加（Java 版）算法|Java

题目描述（题目难度，中等） 【LeetCode|leetcode 2. 两数相加（Java 版）】给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：

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

示例代码

/** * Definition for singly-linked list. * public class ListNode { *int val; *ListNode next; *ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 题目了说了两链表非空，所以不需要空值判断 ListNode sum = new ListNode(0); sum.next = null; ListNode i = sum; //下面这个循环，将l1和l2两链表对应相加，较长的直接接在sum链表后面 while(true){ i.val = l1.val + l2.val; if (l1.next == null && l2.next == null) break; else if (l1.next == null){ i.next = l2.next ; break; }else if (l2.next == null){ i.next = l1.next; break; }else{ l1 = l1.next; l2 = l2.next; i.next = new ListNode(0); i = i.next; i.next = null; } } i = sum; //负责将大于10的结点进行进位处理 while(true){ if(i.val >= 10){ if(i.next != null){ i.val = i.val % 10; //取个位数 i = i.next; i.val += 1; //应该要知道i.val不会超过19，所以直接进1即可，不需要判断十位 }else{ i.val = i.val % 10; i.next = new ListNode(1); i.next.next = null; break; } }else if(i.next == null) break; else i = i.next; } return sum; } }

思路解析这个题目的本意是模拟大整数相加，是一个链表类问题。题目本身不是很难，链表类的题目最主要是要细心，注意，要保持结果链表尾结点的 next 指针为空。
题目也有注释，应该看起来不困难。整体的思路就是：

将输入的两链表，对应结点相加，先不考虑进位，否则代码要复杂得多，感兴趣的可以自己试一下，我也是试了之后才知道的(^&^)。这里要注意的点就是，两个链表极有可能不等长，所以不是一直对应结点相加下去就可以，还要判断是否某条链表已经走到末尾了，如果是则直接将令一链表的剩余结点，链到和链表里即可。
和链表中的结点很可能加成两位数了，此时再遍历一遍和链表进行进位即可。考虑极端情况，就算两个最大的个位数相加再加一个进位，也才 19。所以和链表结点里的值最大只能为 19。当需要进位时，只需要取出个位，而不用取十位，直接后结点加 1 即可。