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

---

Solution1: iterative

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {                ListNode rstHead = new ListNode(0);        ListNode rst = rstHead;        int carry = 0;                while(l1 != null || l2 != null || carry != 0){                        int val = carry;            if(l1!=null) val+=l1.val;            if(l2!=null) val+=l2.val;                        ListNode node = new ListNode(val % 10);                        rst.next = node;            rst = rst.next;                        carry = val / 10;            if(l1!=null) l1 = l1.next;            if(l2!=null) l2 = l2.next;                    }                return rstHead.next;            }}

 

Solution2: Recursive

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {                return helper(l1, l2, 0);            }        public ListNode helper(ListNode n1, ListNode n2, int carry) {        if (n1 == null && n2 == null && carry == 0)            return null;        ListNode node;        int val = carry;                if (n1 != null)            val += n1.val;        if (n2 != null)            val += n2.val;                node = new ListNode(val % 10);                // recursive        if(n1 != null || n2 != null || val > 10){            if(n1 != null)                n1 = n1.next;            if(n2 != null)                n2 = n2.next;            ListNode nextNode = helper(n1,n2, val/10);            node.next = nextNode;        }        return node;    }}