445. Add Two Numbers II

Q:

You are given two linked lists representing two non-negative numbers. 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

A:

把长的先取下后面相同长度的那一段， 对其后，用recursive加起来计算。
同样的思路，处理进位

public class Solution {
    private int carry = 0;
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // l1 , l2 != null
        int len1 = getLen(l1), len2= getLen(l2);
        if(len1<len2)
            return addTwoNumbers(l2,l1);
        ListNode header = new ListNode(0);
        header.next = l1;
        ListNode pre = header;
        carry = 0;
        for(int i =0;i<len1-len2;i++)
            pre = pre.next;
        
        ListNode res = helper(pre.next, l2);
        // recursive to add carry to the front
        add1Recursive(header.next, len1-len2);
        if(carry == 1){
            ListNode newHead = new ListNode(1);
            newHead.next = header.next;
            header.next = newHead;
        }
        return header.next;
    }
    private void add1Recursive(ListNode cur, int k){// k nodes after header
        if(carry == 0 || k == 0)
            return ;
        add1Recursive(cur.next, k-1);
        // add carry , regardless its value
        int sum = cur.val + carry;
        carry = sum/10;
        cur.val = sum %10;
    }
    private ListNode helper(ListNode l1, ListNode l2){
        // l1 and l2 are the same length
        if(l1.next == null){
            int sum = l1.val + l2.val + carry;
            carry = sum/10;
            l1.val = sum %10;
        }else{
            l1.next = helper(l1.next, l2.next);
            int sum = l1.val + l2.val + carry;
            carry = sum/10;
            l1.val = sum %10;
        }
        return l1;
    }

    private int getLen(ListNode head){
        int len = 0;
        while(head != null){
            head = head.next;
            len++;
        }
        return len;
    }
}
 

Errors: