/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 /* use stack, without midifying the list */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while(l1 != null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while(l2 != null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        ListNode head = new ListNode(0);
        int sum = 0;
        while(!stack1.empty() || !stack2.empty()){
            if(!stack1.empty()) sum += stack1.pop();
            if(!stack2.empty()) sum += stack2.pop();
            head.val = sum % 10;
            /* take care of carry */
            ListNode carry = new ListNode(sum / 10);
            carry.next = head;
            head = carry;
            sum /= 10;/* get the carry */
        }
        return head.val == 0 ? head.next : head;
    }
}

/* recursive solution */
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      int size1 = getLength(l1);
      int size2 = getLength(l2);
      ListNode head = new ListNode(1);
      // Make sure l1.length >= l2.length
      head.next = size1 < size2 ? helper(l2, l1, size2 - size1) : helper(l1, l2, size1 - size2);
      // Handle the first digit
      if (head.next.val > 9) {
          head.next.val = head.next.val % 10;
          return head;
      }
      return head.next;
  }
  // get length of the list
  public int getLength(ListNode l) {
      int count = 0;
      while(l != null) {
          l = l.next;
          count++;
      }
      return count;
  }
  // offset is the difference of length between l1 and l2
  public ListNode helper(ListNode l1, ListNode l2, int offset) {
      if (l1 == null) return null;
      // check whether l1 becomes the same length as l2
      ListNode result = offset == 0 ? new ListNode(l1.val + l2.val) : new ListNode(l1.val);
      ListNode post = offset == 0 ? helper(l1.next, l2.next, 0) : helper(l1.next, l2, offset - 1);
      // handle carry
      if (post != null && post.val > 9) {
          result.val += 1;
          post.val = post.val % 10;
      }
      // combine nodes
      result.next = post;
      return result;
  }