You are given two non-empty linked lists representing two non-negative integers. 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.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
Related Topics: Linked List, Math
解题思路：由于代表两个数的链表已经逆序，从个位开始计算，所以结果中每一位是由对应位置的两个数相加，以及前一位的进位组成的。结果链表的最前面设一个dummy node，便于最后返回结果的处理，直接返回dummy.next。
Time Complexity: O(n), Space Complexity: O(1)
Java version:
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 dummy = new ListNode(0); 12 ListNode result = dummy; 13 14 int carry = 0; 15 16 while (l1 != null || l2 != null || carry == 1) { 17 int sum = carry; 18 19 if (l1 != null) { 20 sum += l1.val; 21 l1 = l1.next; 22 } 23 if (l2 != null) { 24 sum += l2.val; 25 l2 = l2.next; 26 } 27 28 ListNode curr = new ListNode(sum % 10); 29 carry = sum / 10; 30 31 result.next = curr; 32 result = result.next; 33 } 34 35 return dummy.next; 36 } 37 }
JavaScript version:
1 /** 2 * Definition for singly-linked list. 3 * function ListNode(val) { 4 * this.val = val; 5 * this.next = null; 6 * } 7 */ 8 /** 9 * @param {ListNode} l1 10 * @param {ListNode} l2 11 * @return {ListNode} 12 */ 13 var addTwoNumbers = function(l1, l2) { 14 var dummy = new ListNode(0); 15 var head = dummy; 16 17 var carry = 0; 18 19 while (l1 != null || l2 != null || carry == 1) { 20 var sum = carry; 21 22 if (l1 != null) { 23 sum += l1.val; 24 l1 = l1.next; 25 } 26 if (l2 != null) { 27 sum += l2.val; 28 l2 = l2.next; 29 } 30 // 注意这里javascript除法会产生float 31 carry = Math.floor(sum / 10); 32 var curr = new ListNode(sum % 10); 33 head.next = curr; 34 head = head.next; 35 } 36 37 return dummy.next; 38 };
Python version:
1 # Definition for singly-linked list. 2 # class ListNode: 3 # def __init__(self, x): 4 # self.val = x 5 # self.next = None 6 7 class Solution: 8 def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: 9 dummy = ListNode(0) 10 head = dummy 11 12 carry = 0 13 14 while l1 is not None or l2 is not None or carry == 1: 15 sum = carry 16 17 if l1 is not None: 18 sum += l1.val 19 l1 = l1.next 20 if l2 is not None: 21 sum += l2.val 22 l2 = l2.next 23 24 carry = math.floor(sum / 10) 25 curr = ListNode(sum % 10) 26 head.next = curr 27 head = head.next 28 29 return dummy.next
2. Add Two Numbers - Medium - Leetcode解题报告
原文：https://www.cnblogs.com/raymondwang/p/10890932.html