给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

    如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

    您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
    示例：
    输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

    方法一、
    暴力法

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) { val = x; }
    7.  * }
    8.  */
    9. class Solution {
    10.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    11.         int a = 0;
    12.         ListNode sumNode=null;
    13.         ListNode returnNode=null;
    14.         while ((l1!=null||l2!=null)||(a!=0&&l1==null&&l2==null)) {
    15.             int val1=0,val2=0;
    16.             if(l1!=null) {
    17.                 val1 = l1.val;
    18.                 l1=l1.next;
    19.             }
    20.             if(l2!=null) {
    21.                 val2 = l2.val;
    22.                 l2=l2.next;
    24.             }
    25.             Object[] result = add(sumNode, val1, val2, a);
    26.             if(sumNode==null) {
    27.                 returnNode = (ListNode) result[1];
    28.             }
    29.             sumNode = (ListNode) result[1];
    30.             a = (int) result[0];
    31.         }
    32.         return returnNode;
    33.     }
    34.     Object[] add(ListNode node,Integer val1,Integer val2,int a) {
    35.         int num = val1+val2+a;
    36.         ListNode nextNode = new ListNode(num%10);
    37.         if(node==null) {
    38.             node=nextNode;
    39.         }else {
    40.             node.next=nextNode;
    41.             node = nextNode;
    42.         }
    43.         return new Object[]{num/10,node};
    44.     }
    45. }

    结果：
    思路：遍历每一个节点，相加生成新节点
    image.png

    2、官方写法

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) { val = x; }
    7.  * }
    8.  */
    9. class Solution {
    10.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    11.         ListNode dummyHead = new ListNode(0);
    12.     ListNode p = l1, q = l2, curr = dummyHead;
    13.     int carry = 0;
    14.     while (p != null || q != null) {
    15.         int x = (p != null) ? p.val : 0;
    16.         int y = (q != null) ? q.val : 0;
    17.         int sum = carry + x + y;
    18.         carry = sum / 10;
    19.         curr.next = new ListNode(sum % 10);
    20.         curr = curr.next;
    21.         if (p != null) p = p.next;
    22.         if (q != null) q = q.next;
    23.     }
    24.     if (carry > 0) {
    25.         curr.next = new ListNode(carry);
    26.     }
    27.     return dummyHead.next;
    28.     }
    30. }

    一个思路，代码比第一种简洁