02. Add two numbers

#02. Addition of two numbers

difficulty ： secondary

Two are given. Non empty The list of is used to represent two non negative integers . among , Their respective digits are based on The reverse Stored in , And each of their nodes can only store a Numbers .

If , Let's add the two numbers together , A new list will be returned to represent their sum .

You can assume that in addition to the numbers 0 outside , Neither of these numbers 0 start .

Example :

 Input ：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 Output ：7 -> 0 -> 8
 reason ：342 + 465 = 807

Copy

# Violence law

# Ideas

Cyclic cracking

First, define a root node 0

Then define a variable cur You can modify the memory point in the loop

Then define a temp Used to store carry data , Initialize to 0, If there is no carry, reset to 0

The cycle judgment is not empty val, Empty words are 0

Finally, the child nodes of the root node are returned

# Code

/**
 * 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 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int temp = 0;
        ListNode pre = new ListNode(0);
        ListNode listNode = pre;
        while (l1 != null || l2 != null) {
            int i = l1 == null ? 0 : l1.val;
            int j = l2 == null ? 0 : l2.val;
            int sum = i + j + temp;
            temp = sum / 10;
            sum = sum % 10;
            listNode.next = new ListNode(sum);
            listNode = listNode.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if(temp == 1) {
            listNode.next = new ListNode(temp);
        }
        return pre.next;
    }

Copy

# Recursive method

# Ideas

Judge first in recursive method l1 Is it empty and l2 Whether it is empty and whether the carry value is 0

Then judge when calling recursion l1 Is it empty ,l2 Is it empty

# Code

/**
 * 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 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return fun(l1, l2, 0);
    }

    ListNode fun(ListNode l1, ListNode l2, int temp) {
        if (l1 == null && l2 == null && temp == 0) {
            return null;
        }
        int i = l1 == null ? 0 : l1.val;
        int j = l2 == null ? 0 : l2.val;
        int sum = i + j + temp;
        temp = sum / 10;
        sum = sum % 10;
        ListNode listNode = new ListNode(sum);
        listNode.next = fun(l1 != null ? l1.next : null, l2 != null ? l2.next : null, temp);
        return listNode;
    }
}

Copy