You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

Solution 1

分别将两个链表转换成数字，再相加，再转成链表。
问题：链表代表的数字可能很大，比Integer的最大值都大，造成overflow.

改进，Solution2 （翻转链表）

image.png

需要考虑进位

image.png

Solution 3

如果follow up 不允许改变原始链表的结构，可以用stack，后进先出。

Code （翻转）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {                
        // solution1 reverse the linkedlist
        if (l1 == null)
        {
            return l2;
        }
        else if (l2 == null)
        {
            return l1;
        }
        
        // reverse l1 and l2
        l1 = reverseNumbers (l1);
        l2 = reverseNumbers (l2);
        
        // add two reversed numbers
        int increase = 0;
        ListNode dummy = new ListNode (0);
        ListNode tempNode = dummy;
        while (l1 != null || l2 != null)
        {
            int tempSum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + increase;
            int sum  = tempSum % 10;
            increase = tempSum / 10;
            
            ListNode newNode = new ListNode (sum);
            tempNode.next = newNode;
            tempNode = newNode;
            
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        
        if (increase > 0)
        {
            ListNode newNode = new ListNode (increase);
            tempNode.next = newNode;
        }
        
        // reverse list again
        return reverseNumbers (dummy.next);
    }
    
    public ListNode reverseNumbers (ListNode head)
    {
        ListNode prev = null;
        ListNode currentNode = head;
        
        while (currentNode != null)
        {
            ListNode next = currentNode.next;
            currentNode.next = prev;
            prev = currentNode;
            currentNode = next;
        }
        
        return prev;
    }
}