2、两数相加-LeetCode

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

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

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

---

解决思路：
①审题：该题实际上是遍历两个链表各节点值相加并add到新链表，当有进位时加1
②步骤：循环遍历，新节点值为遍历节点值相加 sum%10
              下一次遍历时+上一次 sum/10；
              返回新链表

---

 public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { 
        val = x; 
  }
}  

---

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

    ListNode c1 = l1;
    ListNode c2 = l2;
    //返回的新链表
    ListNode sentinel = new ListNode(0);
    ListNode d = sentinel;
    //两节点相加值
    int sum = 0;
    while (c1 != null || c2 != null) {
        //这里除以10得到的值为上一次遍历相加值的进位，按题目须加到下一次遍历
        sum /= 10;
        if (c1 != null) {
            sum += c1.val;
            c1 = c1.next;
        }
        if (c2 != null) {
            sum += c2.val;
            c2 = c2.next;
        }
        //新链表每次增加节点，其值按题目要求为 %10
        d.next = new ListNode(sum % 10);
        //移动指针继续遍历
        d = d.next;
    }
    //遍历结束后，判断最后一次遍历是否仍有相加值超过10，有则必须再增加一个节点，其val=1
    if (sum / 10 == 1)
        d.next = new ListNode(1);
    //这里返回的是从头结点开始
    return sentinel.next;

}