Description

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

Reverse and Add, time O(n), space O(1)

reverse list之后就变成了"Add Two Numbers"那道题。

/**
 * 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) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        ListNode l = add(l1, l2);
        return reverse(l);
    }
    
    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        
        return pre;
    }
    
    public ListNode add(ListNode p, ListNode q) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        int carry = 0;
        
        while (p != null || q != null) {
            if (p != null) {
                carry += p.val;
                p = p.next;
            }
            
            if (q != null) {
                carry += q.val;
                q = q.next;
            }
            
            tail.next = new ListNode(carry % 10);
            tail = tail.next;
            carry /= 10;
        }
        
        if (carry != 0) {
            tail.next = new ListNode(carry);
        }
        
        return dummy.next;
    }
}

Follow up: Stack, time O(n), space O(n)

用递归不太好写，还是Stack大法好。

/**
 * 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) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        push(l1, s1);
        push(l2, s2);
        
        int carry = 0;
        ListNode tail = null;
        
        while (!s1.empty() || !s2.empty()) {
            if (!s1.empty()) {
                carry += s1.pop();
            }
            
            if (!s2.empty()) {
                carry += s2.pop();
            }
            
            ListNode curr = new ListNode(carry % 10);
            curr.next = tail;
            tail = curr;
            carry /= 10;
        }
        
        if (carry != 0) {
            ListNode curr = new ListNode(carry);
            curr.next = tail;
            tail = curr;
        }
        
        return tail;
    }
    
    public void push(ListNode head, Stack<Integer> stack) {
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
    }
}