Add two numbers

Give you two non empty linked lists to represent two non negative integers. They store each number in reverse order, and each node can store only one number.

Please add the two numbers and return a linked list representing sum in the same form.

You can assume that neither number starts with 0 except the number 0.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output:[7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output:[0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output:[8,9,9,9,0,0,0,1]

Tips:

• The number of nodes in each linked list is within the range [1, 100]
• 0 <= Node.val <= 9
• The number represented in the title data guarantee list does not contain leading zeros

Related Topics

recursion

Linked list

mathematics

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

1.iteration
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0),cursor = root;
        int carry = 0;//Represents carry
        while(l1!=null || l2!=null || carry!=0){
            int a = l1!=null ? l1.val : 0;//Judge whether the node is empty. If it is empty, directly assign a to 0, which can effectively avoid calling L1 Null pointer exception in val            
            int b = l2!=null ? l2.val : 0;//Judge whether the node is empty
            int sum = a+b+carry;//If the last carry was, the carry is 1
            carry = sum/10;

            ListNode new_node = new ListNode(sum%10);//Generate a new node
            cursor.next = new_node;
            cursor = new_node;

            if(l1!=null) l1 = l1.next;
            if(l2!=null) l2 = l2.next;

        }

        return root.next;
    }
}


2.recursion
	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // Calculate the sum of two node values
        int val = l1.val + l2.val;
        // Calculate carry value: whether the sum of two nodes is greater than 10
        int carry = val / 10;
        // Whether the recursive termination condition is satisfied: there is no next in both stages
        if (l1.next == null && l2.next == null) {
            // The termination conditions have been met, but there are two cases. Whether the sum of the last two nodes is greater than 10. If it is greater than 10, carry is required. Otherwise, return directly
            return val < 10 ? new ListNode(val) : new ListNode(val % 10, new ListNode(carry));
        }
        // Create a node object. Each node can only save numbers from 0 to 9, so take the remainder of 10
        ListNode node = new ListNode(val%10);
        // Handle the inconsistency of the length of two linked lists. The linked list with short length shall be supplemented with carry value
        if (l1.next == null) {
            l1.next = new ListNode(carry);
        } else if (l2.next == null) {
            l2.next = new ListNode(carry);
        } else {
            // The two linked lists have next nodes. Add carry to the next node, i.e. + 1,l1 and l2
            l1.next.val += carry;
        }
        // Recursive accumulation
        node.next = addTwoNumbers(l1.next, l2.next);
        return node;
    }

//leetcode submit region end(Prohibit modification and deletion)

Summary:

​ Here, instead of adding the values of each linked list first and then converting them into a linked list (dull, I thought so at the beginning), the two linked lists are added successively from the head of the linked list to the tail of the linked list to determine whether to carry (set a variable, and the value of this variable is either non carry 0 or carry 1) to determine the situation of the next node (that is, add this variable directly). The loop does not end until both linked lists are empty and the carry is 0.

Recursive error prone:

​ At first, I created a new variable in the loop, which obviously didn't work. After this cycle, this variable does not exist, so at the beginning, the root linked list is declared to store the head node of the destination linked list, and then a cursor cursor pointer is declared to traverse the whole linked list. The newly created variables in the cycle are also assigned to cursor variables (operated by cursor variables), so that these newly created nodes can exist all the time after the cycle.

Iteration error prone:

1. The length of the two linked lists may be inconsistent, so the linked list with short length needs to be supplemented with 0 to the same length as the other linked list to avoid null pointer exception due to inconsistent length in the addition process.
2. When the two linked lists are added to the last node, it is necessary to verify whether the carry conditions are met. If the conditions are met, it is necessary to add another bit to save the carry, and then the value of the current node can be taken as the remainder of 10.
3. Be sure to ensure the termination condition of recursion, otherwise you know...