You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (7-> 1 -> 6) + (5 -> 9 -> 2) . That is, 617 + 295.
Output: 2 -> 1 -> 9. That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5). That is, 617 + 295.
Output: 9 -> 1 -> 2. That is, 912.

Hint

• Of course, you could convert the linked lists to integers, compute the sum, and then convert it back to a new linked list. If you did this in an interview, your interviewer would likely accept the answer, and then see if you could do this without converting it to a number and back.
• Try recursion. Suppose you have two lists, A = 1 -> 5 -> 9 (representing 951) and B = 2 - > 3 - >6 - > 7 (representing 7632), and a function that operates on the remainder of the lists (5 - >9 and 3 -> 6 - > 7). Could you use this to create the sum method? What is the relationship between sum(1 -> 5 -> 9, 2 -> 3 -> 6 -> 7) and sum(5 -> 9, 3 -> 6 -> 7)?
• Make sure you have considered linked lists that are not the same length.
• Does your algorithm work on linked lists like 9 -> 7 -> 8 and 6 -> 8 -> 5? Double check that.
• For the follow-up question: The issue is that when the linked lists aren't the same length, the head of one linked list might represent the 1000's place while the other represents the 10's place. What if you made them the same length? Is there a way to modify the linked list to do that, without changing the value it represents?

Solution

由于鏈表已經(jīng)是從低位到高位排列，因此只需要從左至右遍歷兩鏈表取出對應(yīng)位累加肮韧，同時(shí)記錄下進(jìn)位信息即可锄弱，下面是迭代的寫法

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(-1), curNode = dummyHead;
    int carry = 0;
    while (l1 != null || l2 != null) {
        int v1 = l1 == null ? 0 : l1.val;
        int v2 = l2 == null ? 0 : l2.val;
        int sum = v1 + v2 + carry;
        carry = sum / 10;
        curNode.next = new ListNode(sum % 10);
        curNode = curNode.next;
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    if (carry == 1) curNode.next = new ListNode(1);
    return dummyHead.next;
}

此外蚤蔓，還可以通過遞歸來寫

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    else if (l2 == null) return l1;

    int sum = l1.val + l2.val;
    ListNode node = new ListNode(sum % 10);
    node.next = addTwoNumbers(l1.next, l2.next);
    if (sum >= 10) node.next = addTwoNumbers(node.next, new ListNode(1));
    return node;
}