两数相加（链表）
一、问题描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
二、问题分析
可以定义两个指针指向链表，每次对指针值进行相加，相加后进行判断如果大于10，产生进位，就让和对10取模然后放入链表，进位计数器记1，如果没有进位就直接加入链表，进位计数器记0，下次计算的时候连同进位计数器中的值一起计算。
三、算法描述
首先给出代码
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode() {} 7 * ListNode(int val) { this.val = val; } 8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; } 9 * } 10 */ 11 class Solution { 12 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 13 ListNode r = null,k = null; 14 int x = 0; //x记录进位 15 while(l1 != null || l2 != null){ 16 int v1 = l1 != null ? l1.val:0; 17 int v2 = l2 != null ? l2.val:0; 18 int count = v1+v2+x; 19 if(count >= 10){ 20 x = count / 10; 21 count = count%10; 22 }else{ 23 x=0; 24 } 25 if(r == null){ 26 r = k = new ListNode(count); 27 }else{ 28 k.next = new ListNode(count); 29 k = k.next; 30 } 31 if(l1 != null){ 32 l1 = l1.next; 33 } 34 if(l2 != null){ 35 l2 = l2.next; 36 } 37 } 38 if(x != 0){ 39 k.next = new ListNode(x); 40 } 41 return r; 42 } 43 }
只要两个链表有一个没有遍历完就继续遍历下去，但是已经遍历完的链表就不再取值，只需要计算进位和未遍历完的链表的值就行。在循环完成后，如果进位计数器不为0说明整体进了1位，那么就要在最后加一位。
四、总结
如果题干给出的不是逆序链表，那么可以多加一步反转链表，这样就能转化成这道题。
原文：https://www.cnblogs.com/zyq79434/p/14994887.html