题目

地址：https://leetcode-cn.com/problems/add-two-numbers/
难度：中等
描述：
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
2. 两数相加 - 图1
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

问题分析

要对头结点进行操作时，考虑创建哑节点dummy，使用dummy->next表示真正的头节点。这样可以避免处理头节点为空的边界问题。
2. 两数相加 - 图2
从最低有效位也就是列表 l1和 l2 的表头开始相加。注意需要考虑到进位的情况！

题解

  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 listNode = new ListNode();
  12.         ListNode p = l1, q = l2, cur = listNode;
  13.         //carry 表示进位数
  14.         int carry = 0;
  15.         while (p != null || q != null){
  16.             //去除节点的值
  17.             int x = (p == null)? 0 : p.val;
  18.             int y = (q == null)? 0 : q.val;
  20.             //进位 + l1的值 + l2的值
  21.             int sum = carry + x + y;
  22.             //计算 进位
  23.             carry = sum / 10;
  24.             //当前节点指向新创建的节点
  25.             cur.next = new ListNode(sum % 10);
  26.             //修改指向当前节点的指针
  27.             cur = cur.next;
  28.             //节点后移一位
  29.             if(p != null) p = p.next;
  30.             if(q != null) q = q.next;
  31.         }
  32.         if (carry > 0){//如果还有进位未处理，添加节点
  33.             cur.next = new ListNode(carry);
  34.         }
  35.         //返回第二个节点，因为第一个节点为0，
  36.         return listNode.next;
  37.     }
  38. }