给两个链表，分别用于表示两个非负数字。数的每一位在链表中反序存放（e.g. 2->4->3代表数342），且每个节点一位。对这两个数求和并返回，结果也用链表表示。
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8
定义四个变量：
*res = ( *i + *j + k ) %10;
k = ( *i + *j + k ) / 10;
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 14 if( l1 == null ) return l2; 15 if( l2 == null ) return l1; 16 17 int quotient = 0; 18 ListNode p = new ListNode(0); 19 p.next = l1; //use l1 as the result link list 20 ListNode q = l2; 21 while( p.next!=null && q!=null ){ 22 p.next.val = p.next.val + q.val + quotient; 23 quotient = p.next.val / 10; 24 p.next.val %= 10; 25 p = p.next; 26 q = q.next; 27 } 28 if( q != null ) p.next = q; 29 while( p.next != null && quotient != 0 ){ 30 p.next.val += quotient; 31 quotient = p.next.val / 10; 32 p.next.val %= 10; 33 p = p.next; 34 } 35 if( quotient != 0 ) 36 p.next = new ListNode(quotient); 37 38 return l1; 39 } 40 }
算法遍历链表，时间复杂度O(n)
原文：http://www.cnblogs.com/hf-cherish/p/4567288.html
